1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2007 Oracle. All rights reserved.
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>
22 #include "print-tree.h"
26 #include "free-space-cache.h"
27 #include "free-space-tree.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"
36 #include "rcu-string.h"
38 #include "dev-replace.h"
40 #undef SCRAMBLE_DELAYED_REFS
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
);
61 static int block_group_bits(struct btrfs_block_group
*cache
, u64 bits
)
63 return (cache
->flags
& bits
) == bits
;
66 int btrfs_add_excluded_extent(struct btrfs_fs_info
*fs_info
,
67 u64 start
, u64 num_bytes
)
69 u64 end
= start
+ num_bytes
- 1;
70 set_extent_bits(&fs_info
->excluded_extents
, start
, end
,
75 void btrfs_free_excluded_extents(struct btrfs_block_group
*cache
)
77 struct btrfs_fs_info
*fs_info
= cache
->fs_info
;
81 end
= start
+ cache
->length
- 1;
83 clear_extent_bits(&fs_info
->excluded_extents
, start
, end
,
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
)
92 struct btrfs_path
*path
;
94 path
= btrfs_alloc_path();
100 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
101 ret
= btrfs_search_slot(NULL
, fs_info
->extent_root
, &key
, path
, 0, 0);
102 btrfs_free_path(path
);
107 * helper function to lookup reference count and flags of a tree block.
109 * the head node for delayed ref is used to store the sum of all the
110 * reference count modifications queued up in the rbtree. the head
111 * node may also store the extent flags to set. This way you can check
112 * to see what the reference count and extent flags would be if all of
113 * the delayed refs are not processed.
115 int btrfs_lookup_extent_info(struct btrfs_trans_handle
*trans
,
116 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
117 u64 offset
, int metadata
, u64
*refs
, u64
*flags
)
119 struct btrfs_delayed_ref_head
*head
;
120 struct btrfs_delayed_ref_root
*delayed_refs
;
121 struct btrfs_path
*path
;
122 struct btrfs_extent_item
*ei
;
123 struct extent_buffer
*leaf
;
124 struct btrfs_key key
;
131 * If we don't have skinny metadata, don't bother doing anything
134 if (metadata
&& !btrfs_fs_incompat(fs_info
, SKINNY_METADATA
)) {
135 offset
= fs_info
->nodesize
;
139 path
= btrfs_alloc_path();
144 path
->skip_locking
= 1;
145 path
->search_commit_root
= 1;
149 key
.objectid
= bytenr
;
152 key
.type
= BTRFS_METADATA_ITEM_KEY
;
154 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
156 ret
= btrfs_search_slot(NULL
, fs_info
->extent_root
, &key
, path
, 0, 0);
160 if (ret
> 0 && metadata
&& key
.type
== BTRFS_METADATA_ITEM_KEY
) {
161 if (path
->slots
[0]) {
163 btrfs_item_key_to_cpu(path
->nodes
[0], &key
,
165 if (key
.objectid
== bytenr
&&
166 key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
167 key
.offset
== fs_info
->nodesize
)
173 leaf
= path
->nodes
[0];
174 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
175 if (item_size
>= sizeof(*ei
)) {
176 ei
= btrfs_item_ptr(leaf
, path
->slots
[0],
177 struct btrfs_extent_item
);
178 num_refs
= btrfs_extent_refs(leaf
, ei
);
179 extent_flags
= btrfs_extent_flags(leaf
, ei
);
182 btrfs_print_v0_err(fs_info
);
184 btrfs_abort_transaction(trans
, ret
);
186 btrfs_handle_fs_error(fs_info
, ret
, NULL
);
191 BUG_ON(num_refs
== 0);
201 delayed_refs
= &trans
->transaction
->delayed_refs
;
202 spin_lock(&delayed_refs
->lock
);
203 head
= btrfs_find_delayed_ref_head(delayed_refs
, bytenr
);
205 if (!mutex_trylock(&head
->mutex
)) {
206 refcount_inc(&head
->refs
);
207 spin_unlock(&delayed_refs
->lock
);
209 btrfs_release_path(path
);
212 * Mutex was contended, block until it's released and try
215 mutex_lock(&head
->mutex
);
216 mutex_unlock(&head
->mutex
);
217 btrfs_put_delayed_ref_head(head
);
220 spin_lock(&head
->lock
);
221 if (head
->extent_op
&& head
->extent_op
->update_flags
)
222 extent_flags
|= head
->extent_op
->flags_to_set
;
224 BUG_ON(num_refs
== 0);
226 num_refs
+= head
->ref_mod
;
227 spin_unlock(&head
->lock
);
228 mutex_unlock(&head
->mutex
);
230 spin_unlock(&delayed_refs
->lock
);
232 WARN_ON(num_refs
== 0);
236 *flags
= extent_flags
;
238 btrfs_free_path(path
);
243 * Back reference rules. Back refs have three main goals:
245 * 1) differentiate between all holders of references to an extent so that
246 * when a reference is dropped we can make sure it was a valid reference
247 * before freeing the extent.
249 * 2) Provide enough information to quickly find the holders of an extent
250 * if we notice a given block is corrupted or bad.
252 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
253 * maintenance. This is actually the same as #2, but with a slightly
254 * different use case.
256 * There are two kinds of back refs. The implicit back refs is optimized
257 * for pointers in non-shared tree blocks. For a given pointer in a block,
258 * back refs of this kind provide information about the block's owner tree
259 * and the pointer's key. These information allow us to find the block by
260 * b-tree searching. The full back refs is for pointers in tree blocks not
261 * referenced by their owner trees. The location of tree block is recorded
262 * in the back refs. Actually the full back refs is generic, and can be
263 * used in all cases the implicit back refs is used. The major shortcoming
264 * of the full back refs is its overhead. Every time a tree block gets
265 * COWed, we have to update back refs entry for all pointers in it.
267 * For a newly allocated tree block, we use implicit back refs for
268 * pointers in it. This means most tree related operations only involve
269 * implicit back refs. For a tree block created in old transaction, the
270 * only way to drop a reference to it is COW it. So we can detect the
271 * event that tree block loses its owner tree's reference and do the
272 * back refs conversion.
274 * When a tree block is COWed through a tree, there are four cases:
276 * The reference count of the block is one and the tree is the block's
277 * owner tree. Nothing to do in this case.
279 * The reference count of the block is one and the tree is not the
280 * block's owner tree. In this case, full back refs is used for pointers
281 * in the block. Remove these full back refs, add implicit back refs for
282 * every pointers in the new block.
284 * The reference count of the block is greater than one and the tree is
285 * the block's owner tree. In this case, implicit back refs is used for
286 * pointers in the block. Add full back refs for every pointers in the
287 * block, increase lower level extents' reference counts. The original
288 * implicit back refs are entailed to the new block.
290 * The reference count of the block is greater than one and the tree is
291 * not the block's owner tree. Add implicit back refs for every pointer in
292 * the new block, increase lower level extents' reference count.
294 * Back Reference Key composing:
296 * The key objectid corresponds to the first byte in the extent,
297 * The key type is used to differentiate between types of back refs.
298 * There are different meanings of the key offset for different types
301 * File extents can be referenced by:
303 * - multiple snapshots, subvolumes, or different generations in one subvol
304 * - different files inside a single subvolume
305 * - different offsets inside a file (bookend extents in file.c)
307 * The extent ref structure for the implicit back refs has fields for:
309 * - Objectid of the subvolume root
310 * - objectid of the file holding the reference
311 * - original offset in the file
312 * - how many bookend extents
314 * The key offset for the implicit back refs is hash of the first
317 * The extent ref structure for the full back refs has field for:
319 * - number of pointers in the tree leaf
321 * The key offset for the implicit back refs is the first byte of
324 * When a file extent is allocated, The implicit back refs is used.
325 * the fields are filled in:
327 * (root_key.objectid, inode objectid, offset in file, 1)
329 * When a file extent is removed file truncation, we find the
330 * corresponding implicit back refs and check the following fields:
332 * (btrfs_header_owner(leaf), inode objectid, offset in file)
334 * Btree extents can be referenced by:
336 * - Different subvolumes
338 * Both the implicit back refs and the full back refs for tree blocks
339 * only consist of key. The key offset for the implicit back refs is
340 * objectid of block's owner tree. The key offset for the full back refs
341 * is the first byte of parent block.
343 * When implicit back refs is used, information about the lowest key and
344 * level of the tree block are required. These information are stored in
345 * tree block info structure.
349 * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
350 * is_data == BTRFS_REF_TYPE_DATA, data type is requiried,
351 * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
353 int btrfs_get_extent_inline_ref_type(const struct extent_buffer
*eb
,
354 struct btrfs_extent_inline_ref
*iref
,
355 enum btrfs_inline_ref_type is_data
)
357 int type
= btrfs_extent_inline_ref_type(eb
, iref
);
358 u64 offset
= btrfs_extent_inline_ref_offset(eb
, iref
);
360 if (type
== BTRFS_TREE_BLOCK_REF_KEY
||
361 type
== BTRFS_SHARED_BLOCK_REF_KEY
||
362 type
== BTRFS_SHARED_DATA_REF_KEY
||
363 type
== BTRFS_EXTENT_DATA_REF_KEY
) {
364 if (is_data
== BTRFS_REF_TYPE_BLOCK
) {
365 if (type
== BTRFS_TREE_BLOCK_REF_KEY
)
367 if (type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
370 * Every shared one has parent tree block,
371 * which must be aligned to sector size.
374 IS_ALIGNED(offset
, eb
->fs_info
->sectorsize
))
377 } else if (is_data
== BTRFS_REF_TYPE_DATA
) {
378 if (type
== BTRFS_EXTENT_DATA_REF_KEY
)
380 if (type
== BTRFS_SHARED_DATA_REF_KEY
) {
383 * Every shared one has parent tree block,
384 * which must be aligned to sector size.
387 IS_ALIGNED(offset
, eb
->fs_info
->sectorsize
))
391 ASSERT(is_data
== BTRFS_REF_TYPE_ANY
);
396 btrfs_print_leaf((struct extent_buffer
*)eb
);
397 btrfs_err(eb
->fs_info
,
398 "eb %llu iref 0x%lx invalid extent inline ref type %d",
399 eb
->start
, (unsigned long)iref
, type
);
402 return BTRFS_REF_TYPE_INVALID
;
405 u64
hash_extent_data_ref(u64 root_objectid
, u64 owner
, u64 offset
)
407 u32 high_crc
= ~(u32
)0;
408 u32 low_crc
= ~(u32
)0;
411 lenum
= cpu_to_le64(root_objectid
);
412 high_crc
= btrfs_crc32c(high_crc
, &lenum
, sizeof(lenum
));
413 lenum
= cpu_to_le64(owner
);
414 low_crc
= btrfs_crc32c(low_crc
, &lenum
, sizeof(lenum
));
415 lenum
= cpu_to_le64(offset
);
416 low_crc
= btrfs_crc32c(low_crc
, &lenum
, sizeof(lenum
));
418 return ((u64
)high_crc
<< 31) ^ (u64
)low_crc
;
421 static u64
hash_extent_data_ref_item(struct extent_buffer
*leaf
,
422 struct btrfs_extent_data_ref
*ref
)
424 return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf
, ref
),
425 btrfs_extent_data_ref_objectid(leaf
, ref
),
426 btrfs_extent_data_ref_offset(leaf
, ref
));
429 static int match_extent_data_ref(struct extent_buffer
*leaf
,
430 struct btrfs_extent_data_ref
*ref
,
431 u64 root_objectid
, u64 owner
, u64 offset
)
433 if (btrfs_extent_data_ref_root(leaf
, ref
) != root_objectid
||
434 btrfs_extent_data_ref_objectid(leaf
, ref
) != owner
||
435 btrfs_extent_data_ref_offset(leaf
, ref
) != offset
)
440 static noinline
int lookup_extent_data_ref(struct btrfs_trans_handle
*trans
,
441 struct btrfs_path
*path
,
442 u64 bytenr
, u64 parent
,
444 u64 owner
, u64 offset
)
446 struct btrfs_root
*root
= trans
->fs_info
->extent_root
;
447 struct btrfs_key key
;
448 struct btrfs_extent_data_ref
*ref
;
449 struct extent_buffer
*leaf
;
455 key
.objectid
= bytenr
;
457 key
.type
= BTRFS_SHARED_DATA_REF_KEY
;
460 key
.type
= BTRFS_EXTENT_DATA_REF_KEY
;
461 key
.offset
= hash_extent_data_ref(root_objectid
,
466 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
478 leaf
= path
->nodes
[0];
479 nritems
= btrfs_header_nritems(leaf
);
481 if (path
->slots
[0] >= nritems
) {
482 ret
= btrfs_next_leaf(root
, path
);
488 leaf
= path
->nodes
[0];
489 nritems
= btrfs_header_nritems(leaf
);
493 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
494 if (key
.objectid
!= bytenr
||
495 key
.type
!= BTRFS_EXTENT_DATA_REF_KEY
)
498 ref
= btrfs_item_ptr(leaf
, path
->slots
[0],
499 struct btrfs_extent_data_ref
);
501 if (match_extent_data_ref(leaf
, ref
, root_objectid
,
504 btrfs_release_path(path
);
516 static noinline
int insert_extent_data_ref(struct btrfs_trans_handle
*trans
,
517 struct btrfs_path
*path
,
518 u64 bytenr
, u64 parent
,
519 u64 root_objectid
, u64 owner
,
520 u64 offset
, int refs_to_add
)
522 struct btrfs_root
*root
= trans
->fs_info
->extent_root
;
523 struct btrfs_key key
;
524 struct extent_buffer
*leaf
;
529 key
.objectid
= bytenr
;
531 key
.type
= BTRFS_SHARED_DATA_REF_KEY
;
533 size
= sizeof(struct btrfs_shared_data_ref
);
535 key
.type
= BTRFS_EXTENT_DATA_REF_KEY
;
536 key
.offset
= hash_extent_data_ref(root_objectid
,
538 size
= sizeof(struct btrfs_extent_data_ref
);
541 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
, size
);
542 if (ret
&& ret
!= -EEXIST
)
545 leaf
= path
->nodes
[0];
547 struct btrfs_shared_data_ref
*ref
;
548 ref
= btrfs_item_ptr(leaf
, path
->slots
[0],
549 struct btrfs_shared_data_ref
);
551 btrfs_set_shared_data_ref_count(leaf
, ref
, refs_to_add
);
553 num_refs
= btrfs_shared_data_ref_count(leaf
, ref
);
554 num_refs
+= refs_to_add
;
555 btrfs_set_shared_data_ref_count(leaf
, ref
, num_refs
);
558 struct btrfs_extent_data_ref
*ref
;
559 while (ret
== -EEXIST
) {
560 ref
= btrfs_item_ptr(leaf
, path
->slots
[0],
561 struct btrfs_extent_data_ref
);
562 if (match_extent_data_ref(leaf
, ref
, root_objectid
,
565 btrfs_release_path(path
);
567 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
569 if (ret
&& ret
!= -EEXIST
)
572 leaf
= path
->nodes
[0];
574 ref
= btrfs_item_ptr(leaf
, path
->slots
[0],
575 struct btrfs_extent_data_ref
);
577 btrfs_set_extent_data_ref_root(leaf
, ref
,
579 btrfs_set_extent_data_ref_objectid(leaf
, ref
, owner
);
580 btrfs_set_extent_data_ref_offset(leaf
, ref
, offset
);
581 btrfs_set_extent_data_ref_count(leaf
, ref
, refs_to_add
);
583 num_refs
= btrfs_extent_data_ref_count(leaf
, ref
);
584 num_refs
+= refs_to_add
;
585 btrfs_set_extent_data_ref_count(leaf
, ref
, num_refs
);
588 btrfs_mark_buffer_dirty(leaf
);
591 btrfs_release_path(path
);
595 static noinline
int remove_extent_data_ref(struct btrfs_trans_handle
*trans
,
596 struct btrfs_path
*path
,
597 int refs_to_drop
, int *last_ref
)
599 struct btrfs_key key
;
600 struct btrfs_extent_data_ref
*ref1
= NULL
;
601 struct btrfs_shared_data_ref
*ref2
= NULL
;
602 struct extent_buffer
*leaf
;
606 leaf
= path
->nodes
[0];
607 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
609 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
610 ref1
= btrfs_item_ptr(leaf
, path
->slots
[0],
611 struct btrfs_extent_data_ref
);
612 num_refs
= btrfs_extent_data_ref_count(leaf
, ref1
);
613 } else if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
614 ref2
= btrfs_item_ptr(leaf
, path
->slots
[0],
615 struct btrfs_shared_data_ref
);
616 num_refs
= btrfs_shared_data_ref_count(leaf
, ref2
);
617 } else if (unlikely(key
.type
== BTRFS_EXTENT_REF_V0_KEY
)) {
618 btrfs_print_v0_err(trans
->fs_info
);
619 btrfs_abort_transaction(trans
, -EINVAL
);
625 BUG_ON(num_refs
< refs_to_drop
);
626 num_refs
-= refs_to_drop
;
629 ret
= btrfs_del_item(trans
, trans
->fs_info
->extent_root
, path
);
632 if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
)
633 btrfs_set_extent_data_ref_count(leaf
, ref1
, num_refs
);
634 else if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
)
635 btrfs_set_shared_data_ref_count(leaf
, ref2
, num_refs
);
636 btrfs_mark_buffer_dirty(leaf
);
641 static noinline u32
extent_data_ref_count(struct btrfs_path
*path
,
642 struct btrfs_extent_inline_ref
*iref
)
644 struct btrfs_key key
;
645 struct extent_buffer
*leaf
;
646 struct btrfs_extent_data_ref
*ref1
;
647 struct btrfs_shared_data_ref
*ref2
;
651 leaf
= path
->nodes
[0];
652 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
654 BUG_ON(key
.type
== BTRFS_EXTENT_REF_V0_KEY
);
657 * If type is invalid, we should have bailed out earlier than
660 type
= btrfs_get_extent_inline_ref_type(leaf
, iref
, BTRFS_REF_TYPE_DATA
);
661 ASSERT(type
!= BTRFS_REF_TYPE_INVALID
);
662 if (type
== BTRFS_EXTENT_DATA_REF_KEY
) {
663 ref1
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
664 num_refs
= btrfs_extent_data_ref_count(leaf
, ref1
);
666 ref2
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
667 num_refs
= btrfs_shared_data_ref_count(leaf
, ref2
);
669 } else if (key
.type
== BTRFS_EXTENT_DATA_REF_KEY
) {
670 ref1
= btrfs_item_ptr(leaf
, path
->slots
[0],
671 struct btrfs_extent_data_ref
);
672 num_refs
= btrfs_extent_data_ref_count(leaf
, ref1
);
673 } else if (key
.type
== BTRFS_SHARED_DATA_REF_KEY
) {
674 ref2
= btrfs_item_ptr(leaf
, path
->slots
[0],
675 struct btrfs_shared_data_ref
);
676 num_refs
= btrfs_shared_data_ref_count(leaf
, ref2
);
683 static noinline
int lookup_tree_block_ref(struct btrfs_trans_handle
*trans
,
684 struct btrfs_path
*path
,
685 u64 bytenr
, u64 parent
,
688 struct btrfs_root
*root
= trans
->fs_info
->extent_root
;
689 struct btrfs_key key
;
692 key
.objectid
= bytenr
;
694 key
.type
= BTRFS_SHARED_BLOCK_REF_KEY
;
697 key
.type
= BTRFS_TREE_BLOCK_REF_KEY
;
698 key
.offset
= root_objectid
;
701 ret
= btrfs_search_slot(trans
, root
, &key
, path
, -1, 1);
707 static noinline
int insert_tree_block_ref(struct btrfs_trans_handle
*trans
,
708 struct btrfs_path
*path
,
709 u64 bytenr
, u64 parent
,
712 struct btrfs_key key
;
715 key
.objectid
= bytenr
;
717 key
.type
= BTRFS_SHARED_BLOCK_REF_KEY
;
720 key
.type
= BTRFS_TREE_BLOCK_REF_KEY
;
721 key
.offset
= root_objectid
;
724 ret
= btrfs_insert_empty_item(trans
, trans
->fs_info
->extent_root
,
726 btrfs_release_path(path
);
730 static inline int extent_ref_type(u64 parent
, u64 owner
)
733 if (owner
< BTRFS_FIRST_FREE_OBJECTID
) {
735 type
= BTRFS_SHARED_BLOCK_REF_KEY
;
737 type
= BTRFS_TREE_BLOCK_REF_KEY
;
740 type
= BTRFS_SHARED_DATA_REF_KEY
;
742 type
= BTRFS_EXTENT_DATA_REF_KEY
;
747 static int find_next_key(struct btrfs_path
*path
, int level
,
748 struct btrfs_key
*key
)
751 for (; level
< BTRFS_MAX_LEVEL
; level
++) {
752 if (!path
->nodes
[level
])
754 if (path
->slots
[level
] + 1 >=
755 btrfs_header_nritems(path
->nodes
[level
]))
758 btrfs_item_key_to_cpu(path
->nodes
[level
], key
,
759 path
->slots
[level
] + 1);
761 btrfs_node_key_to_cpu(path
->nodes
[level
], key
,
762 path
->slots
[level
] + 1);
769 * look for inline back ref. if back ref is found, *ref_ret is set
770 * to the address of inline back ref, and 0 is returned.
772 * if back ref isn't found, *ref_ret is set to the address where it
773 * should be inserted, and -ENOENT is returned.
775 * if insert is true and there are too many inline back refs, the path
776 * points to the extent item, and -EAGAIN is returned.
778 * NOTE: inline back refs are ordered in the same way that back ref
779 * items in the tree are ordered.
781 static noinline_for_stack
782 int lookup_inline_extent_backref(struct btrfs_trans_handle
*trans
,
783 struct btrfs_path
*path
,
784 struct btrfs_extent_inline_ref
**ref_ret
,
785 u64 bytenr
, u64 num_bytes
,
786 u64 parent
, u64 root_objectid
,
787 u64 owner
, u64 offset
, int insert
)
789 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
790 struct btrfs_root
*root
= fs_info
->extent_root
;
791 struct btrfs_key key
;
792 struct extent_buffer
*leaf
;
793 struct btrfs_extent_item
*ei
;
794 struct btrfs_extent_inline_ref
*iref
;
804 bool skinny_metadata
= btrfs_fs_incompat(fs_info
, SKINNY_METADATA
);
807 key
.objectid
= bytenr
;
808 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
809 key
.offset
= num_bytes
;
811 want
= extent_ref_type(parent
, owner
);
813 extra_size
= btrfs_extent_inline_ref_size(want
);
814 path
->search_for_extension
= 1;
815 path
->keep_locks
= 1;
820 * Owner is our level, so we can just add one to get the level for the
821 * block we are interested in.
823 if (skinny_metadata
&& owner
< BTRFS_FIRST_FREE_OBJECTID
) {
824 key
.type
= BTRFS_METADATA_ITEM_KEY
;
829 ret
= btrfs_search_slot(trans
, root
, &key
, path
, extra_size
, 1);
836 * We may be a newly converted file system which still has the old fat
837 * extent entries for metadata, so try and see if we have one of those.
839 if (ret
> 0 && skinny_metadata
) {
840 skinny_metadata
= false;
841 if (path
->slots
[0]) {
843 btrfs_item_key_to_cpu(path
->nodes
[0], &key
,
845 if (key
.objectid
== bytenr
&&
846 key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
847 key
.offset
== num_bytes
)
851 key
.objectid
= bytenr
;
852 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
853 key
.offset
= num_bytes
;
854 btrfs_release_path(path
);
859 if (ret
&& !insert
) {
862 } else if (WARN_ON(ret
)) {
867 leaf
= path
->nodes
[0];
868 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
869 if (unlikely(item_size
< sizeof(*ei
))) {
871 btrfs_print_v0_err(fs_info
);
872 btrfs_abort_transaction(trans
, err
);
876 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
877 flags
= btrfs_extent_flags(leaf
, ei
);
879 ptr
= (unsigned long)(ei
+ 1);
880 end
= (unsigned long)ei
+ item_size
;
882 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
&& !skinny_metadata
) {
883 ptr
+= sizeof(struct btrfs_tree_block_info
);
887 if (owner
>= BTRFS_FIRST_FREE_OBJECTID
)
888 needed
= BTRFS_REF_TYPE_DATA
;
890 needed
= BTRFS_REF_TYPE_BLOCK
;
898 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
899 type
= btrfs_get_extent_inline_ref_type(leaf
, iref
, needed
);
900 if (type
== BTRFS_REF_TYPE_INVALID
) {
908 ptr
+= btrfs_extent_inline_ref_size(type
);
912 if (type
== BTRFS_EXTENT_DATA_REF_KEY
) {
913 struct btrfs_extent_data_ref
*dref
;
914 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
915 if (match_extent_data_ref(leaf
, dref
, root_objectid
,
920 if (hash_extent_data_ref_item(leaf
, dref
) <
921 hash_extent_data_ref(root_objectid
, owner
, offset
))
925 ref_offset
= btrfs_extent_inline_ref_offset(leaf
, iref
);
927 if (parent
== ref_offset
) {
931 if (ref_offset
< parent
)
934 if (root_objectid
== ref_offset
) {
938 if (ref_offset
< root_objectid
)
942 ptr
+= btrfs_extent_inline_ref_size(type
);
944 if (err
== -ENOENT
&& insert
) {
945 if (item_size
+ extra_size
>=
946 BTRFS_MAX_EXTENT_ITEM_SIZE(root
)) {
951 * To add new inline back ref, we have to make sure
952 * there is no corresponding back ref item.
953 * For simplicity, we just do not add new inline back
954 * ref if there is any kind of item for this block
956 if (find_next_key(path
, 0, &key
) == 0 &&
957 key
.objectid
== bytenr
&&
958 key
.type
< BTRFS_BLOCK_GROUP_ITEM_KEY
) {
963 *ref_ret
= (struct btrfs_extent_inline_ref
*)ptr
;
966 path
->keep_locks
= 0;
967 path
->search_for_extension
= 0;
968 btrfs_unlock_up_safe(path
, 1);
974 * helper to add new inline back ref
976 static noinline_for_stack
977 void setup_inline_extent_backref(struct btrfs_fs_info
*fs_info
,
978 struct btrfs_path
*path
,
979 struct btrfs_extent_inline_ref
*iref
,
980 u64 parent
, u64 root_objectid
,
981 u64 owner
, u64 offset
, int refs_to_add
,
982 struct btrfs_delayed_extent_op
*extent_op
)
984 struct extent_buffer
*leaf
;
985 struct btrfs_extent_item
*ei
;
988 unsigned long item_offset
;
993 leaf
= path
->nodes
[0];
994 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
995 item_offset
= (unsigned long)iref
- (unsigned long)ei
;
997 type
= extent_ref_type(parent
, owner
);
998 size
= btrfs_extent_inline_ref_size(type
);
1000 btrfs_extend_item(path
, size
);
1002 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
1003 refs
= btrfs_extent_refs(leaf
, ei
);
1004 refs
+= refs_to_add
;
1005 btrfs_set_extent_refs(leaf
, ei
, refs
);
1007 __run_delayed_extent_op(extent_op
, leaf
, ei
);
1009 ptr
= (unsigned long)ei
+ item_offset
;
1010 end
= (unsigned long)ei
+ btrfs_item_size_nr(leaf
, path
->slots
[0]);
1011 if (ptr
< end
- size
)
1012 memmove_extent_buffer(leaf
, ptr
+ size
, ptr
,
1015 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
1016 btrfs_set_extent_inline_ref_type(leaf
, iref
, type
);
1017 if (type
== BTRFS_EXTENT_DATA_REF_KEY
) {
1018 struct btrfs_extent_data_ref
*dref
;
1019 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
1020 btrfs_set_extent_data_ref_root(leaf
, dref
, root_objectid
);
1021 btrfs_set_extent_data_ref_objectid(leaf
, dref
, owner
);
1022 btrfs_set_extent_data_ref_offset(leaf
, dref
, offset
);
1023 btrfs_set_extent_data_ref_count(leaf
, dref
, refs_to_add
);
1024 } else if (type
== BTRFS_SHARED_DATA_REF_KEY
) {
1025 struct btrfs_shared_data_ref
*sref
;
1026 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
1027 btrfs_set_shared_data_ref_count(leaf
, sref
, refs_to_add
);
1028 btrfs_set_extent_inline_ref_offset(leaf
, iref
, parent
);
1029 } else if (type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
1030 btrfs_set_extent_inline_ref_offset(leaf
, iref
, parent
);
1032 btrfs_set_extent_inline_ref_offset(leaf
, iref
, root_objectid
);
1034 btrfs_mark_buffer_dirty(leaf
);
1037 static int lookup_extent_backref(struct btrfs_trans_handle
*trans
,
1038 struct btrfs_path
*path
,
1039 struct btrfs_extent_inline_ref
**ref_ret
,
1040 u64 bytenr
, u64 num_bytes
, u64 parent
,
1041 u64 root_objectid
, u64 owner
, u64 offset
)
1045 ret
= lookup_inline_extent_backref(trans
, path
, ref_ret
, bytenr
,
1046 num_bytes
, parent
, root_objectid
,
1051 btrfs_release_path(path
);
1054 if (owner
< BTRFS_FIRST_FREE_OBJECTID
) {
1055 ret
= lookup_tree_block_ref(trans
, path
, bytenr
, parent
,
1058 ret
= lookup_extent_data_ref(trans
, path
, bytenr
, parent
,
1059 root_objectid
, owner
, offset
);
1065 * helper to update/remove inline back ref
1067 static noinline_for_stack
1068 void update_inline_extent_backref(struct btrfs_path
*path
,
1069 struct btrfs_extent_inline_ref
*iref
,
1071 struct btrfs_delayed_extent_op
*extent_op
,
1074 struct extent_buffer
*leaf
= path
->nodes
[0];
1075 struct btrfs_extent_item
*ei
;
1076 struct btrfs_extent_data_ref
*dref
= NULL
;
1077 struct btrfs_shared_data_ref
*sref
= NULL
;
1085 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
1086 refs
= btrfs_extent_refs(leaf
, ei
);
1087 WARN_ON(refs_to_mod
< 0 && refs
+ refs_to_mod
<= 0);
1088 refs
+= refs_to_mod
;
1089 btrfs_set_extent_refs(leaf
, ei
, refs
);
1091 __run_delayed_extent_op(extent_op
, leaf
, ei
);
1094 * If type is invalid, we should have bailed out after
1095 * lookup_inline_extent_backref().
1097 type
= btrfs_get_extent_inline_ref_type(leaf
, iref
, BTRFS_REF_TYPE_ANY
);
1098 ASSERT(type
!= BTRFS_REF_TYPE_INVALID
);
1100 if (type
== BTRFS_EXTENT_DATA_REF_KEY
) {
1101 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
1102 refs
= btrfs_extent_data_ref_count(leaf
, dref
);
1103 } else if (type
== BTRFS_SHARED_DATA_REF_KEY
) {
1104 sref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
1105 refs
= btrfs_shared_data_ref_count(leaf
, sref
);
1108 BUG_ON(refs_to_mod
!= -1);
1111 BUG_ON(refs_to_mod
< 0 && refs
< -refs_to_mod
);
1112 refs
+= refs_to_mod
;
1115 if (type
== BTRFS_EXTENT_DATA_REF_KEY
)
1116 btrfs_set_extent_data_ref_count(leaf
, dref
, refs
);
1118 btrfs_set_shared_data_ref_count(leaf
, sref
, refs
);
1121 size
= btrfs_extent_inline_ref_size(type
);
1122 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
1123 ptr
= (unsigned long)iref
;
1124 end
= (unsigned long)ei
+ item_size
;
1125 if (ptr
+ size
< end
)
1126 memmove_extent_buffer(leaf
, ptr
, ptr
+ size
,
1129 btrfs_truncate_item(path
, item_size
, 1);
1131 btrfs_mark_buffer_dirty(leaf
);
1134 static noinline_for_stack
1135 int insert_inline_extent_backref(struct btrfs_trans_handle
*trans
,
1136 struct btrfs_path
*path
,
1137 u64 bytenr
, u64 num_bytes
, u64 parent
,
1138 u64 root_objectid
, u64 owner
,
1139 u64 offset
, int refs_to_add
,
1140 struct btrfs_delayed_extent_op
*extent_op
)
1142 struct btrfs_extent_inline_ref
*iref
;
1145 ret
= lookup_inline_extent_backref(trans
, path
, &iref
, bytenr
,
1146 num_bytes
, parent
, root_objectid
,
1150 * We're adding refs to a tree block we already own, this
1151 * should not happen at all.
1153 if (owner
< BTRFS_FIRST_FREE_OBJECTID
) {
1154 btrfs_crit(trans
->fs_info
,
1155 "adding refs to an existing tree ref, bytenr %llu num_bytes %llu root_objectid %llu",
1156 bytenr
, num_bytes
, root_objectid
);
1157 if (IS_ENABLED(CONFIG_BTRFS_DEBUG
)) {
1159 btrfs_crit(trans
->fs_info
,
1160 "path->slots[0]=%d path->nodes[0]:", path
->slots
[0]);
1161 btrfs_print_leaf(path
->nodes
[0]);
1165 update_inline_extent_backref(path
, iref
, refs_to_add
,
1167 } else if (ret
== -ENOENT
) {
1168 setup_inline_extent_backref(trans
->fs_info
, path
, iref
, parent
,
1169 root_objectid
, owner
, offset
,
1170 refs_to_add
, extent_op
);
1176 static int remove_extent_backref(struct btrfs_trans_handle
*trans
,
1177 struct btrfs_path
*path
,
1178 struct btrfs_extent_inline_ref
*iref
,
1179 int refs_to_drop
, int is_data
, int *last_ref
)
1183 BUG_ON(!is_data
&& refs_to_drop
!= 1);
1185 update_inline_extent_backref(path
, iref
, -refs_to_drop
, NULL
,
1187 } else if (is_data
) {
1188 ret
= remove_extent_data_ref(trans
, path
, refs_to_drop
,
1192 ret
= btrfs_del_item(trans
, trans
->fs_info
->extent_root
, path
);
1197 static int btrfs_issue_discard(struct block_device
*bdev
, u64 start
, u64 len
,
1198 u64
*discarded_bytes
)
1201 u64 bytes_left
, end
;
1202 u64 aligned_start
= ALIGN(start
, 1 << 9);
1204 if (WARN_ON(start
!= aligned_start
)) {
1205 len
-= aligned_start
- start
;
1206 len
= round_down(len
, 1 << 9);
1207 start
= aligned_start
;
1210 *discarded_bytes
= 0;
1218 /* Skip any superblocks on this device. */
1219 for (j
= 0; j
< BTRFS_SUPER_MIRROR_MAX
; j
++) {
1220 u64 sb_start
= btrfs_sb_offset(j
);
1221 u64 sb_end
= sb_start
+ BTRFS_SUPER_INFO_SIZE
;
1222 u64 size
= sb_start
- start
;
1224 if (!in_range(sb_start
, start
, bytes_left
) &&
1225 !in_range(sb_end
, start
, bytes_left
) &&
1226 !in_range(start
, sb_start
, BTRFS_SUPER_INFO_SIZE
))
1230 * Superblock spans beginning of range. Adjust start and
1233 if (sb_start
<= start
) {
1234 start
+= sb_end
- start
;
1239 bytes_left
= end
- start
;
1244 ret
= blkdev_issue_discard(bdev
, start
>> 9, size
>> 9,
1247 *discarded_bytes
+= size
;
1248 else if (ret
!= -EOPNOTSUPP
)
1257 bytes_left
= end
- start
;
1261 ret
= blkdev_issue_discard(bdev
, start
>> 9, bytes_left
>> 9,
1264 *discarded_bytes
+= bytes_left
;
1269 static int do_discard_extent(struct btrfs_io_stripe
*stripe
, u64
*bytes
)
1271 struct btrfs_device
*dev
= stripe
->dev
;
1272 struct btrfs_fs_info
*fs_info
= dev
->fs_info
;
1273 struct btrfs_dev_replace
*dev_replace
= &fs_info
->dev_replace
;
1274 u64 phys
= stripe
->physical
;
1275 u64 len
= stripe
->length
;
1279 /* Zone reset on a zoned filesystem */
1280 if (btrfs_can_zone_reset(dev
, phys
, len
)) {
1283 ret
= btrfs_reset_device_zone(dev
, phys
, len
, &discarded
);
1287 if (!btrfs_dev_replace_is_ongoing(dev_replace
) ||
1288 dev
!= dev_replace
->srcdev
)
1291 src_disc
= discarded
;
1293 /* Send to replace target as well */
1294 ret
= btrfs_reset_device_zone(dev_replace
->tgtdev
, phys
, len
,
1296 discarded
+= src_disc
;
1297 } else if (blk_queue_discard(bdev_get_queue(stripe
->dev
->bdev
))) {
1298 ret
= btrfs_issue_discard(dev
->bdev
, phys
, len
, &discarded
);
1309 int btrfs_discard_extent(struct btrfs_fs_info
*fs_info
, u64 bytenr
,
1310 u64 num_bytes
, u64
*actual_bytes
)
1313 u64 discarded_bytes
= 0;
1314 u64 end
= bytenr
+ num_bytes
;
1316 struct btrfs_io_context
*bioc
= NULL
;
1319 * Avoid races with device replace and make sure our bioc has devices
1320 * associated to its stripes that don't go away while we are discarding.
1322 btrfs_bio_counter_inc_blocked(fs_info
);
1324 struct btrfs_io_stripe
*stripe
;
1327 num_bytes
= end
- cur
;
1328 /* Tell the block device(s) that the sectors can be discarded */
1329 ret
= btrfs_map_block(fs_info
, BTRFS_MAP_DISCARD
, cur
,
1330 &num_bytes
, &bioc
, 0);
1332 * Error can be -ENOMEM, -ENOENT (no such chunk mapping) or
1333 * -EOPNOTSUPP. For any such error, @num_bytes is not updated,
1334 * thus we can't continue anyway.
1339 stripe
= bioc
->stripes
;
1340 for (i
= 0; i
< bioc
->num_stripes
; i
++, stripe
++) {
1342 struct btrfs_device
*device
= stripe
->dev
;
1344 if (!device
->bdev
) {
1345 ASSERT(btrfs_test_opt(fs_info
, DEGRADED
));
1349 if (!test_bit(BTRFS_DEV_STATE_WRITEABLE
, &device
->dev_state
))
1352 ret
= do_discard_extent(stripe
, &bytes
);
1354 discarded_bytes
+= bytes
;
1355 } else if (ret
!= -EOPNOTSUPP
) {
1357 * Logic errors or -ENOMEM, or -EIO, but
1358 * unlikely to happen.
1360 * And since there are two loops, explicitly
1361 * go to out to avoid confusion.
1363 btrfs_put_bioc(bioc
);
1368 * Just in case we get back EOPNOTSUPP for some reason,
1369 * just ignore the return value so we don't screw up
1370 * people calling discard_extent.
1374 btrfs_put_bioc(bioc
);
1378 btrfs_bio_counter_dec(fs_info
);
1381 *actual_bytes
= discarded_bytes
;
1384 if (ret
== -EOPNOTSUPP
)
1389 /* Can return -ENOMEM */
1390 int btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
1391 struct btrfs_ref
*generic_ref
)
1393 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
1396 ASSERT(generic_ref
->type
!= BTRFS_REF_NOT_SET
&&
1397 generic_ref
->action
);
1398 BUG_ON(generic_ref
->type
== BTRFS_REF_METADATA
&&
1399 generic_ref
->tree_ref
.root
== BTRFS_TREE_LOG_OBJECTID
);
1401 if (generic_ref
->type
== BTRFS_REF_METADATA
)
1402 ret
= btrfs_add_delayed_tree_ref(trans
, generic_ref
, NULL
);
1404 ret
= btrfs_add_delayed_data_ref(trans
, generic_ref
, 0);
1406 btrfs_ref_tree_mod(fs_info
, generic_ref
);
1412 * __btrfs_inc_extent_ref - insert backreference for a given extent
1414 * The counterpart is in __btrfs_free_extent(), with examples and more details
1417 * @trans: Handle of transaction
1419 * @node: The delayed ref node used to get the bytenr/length for
1420 * extent whose references are incremented.
1422 * @parent: If this is a shared extent (BTRFS_SHARED_DATA_REF_KEY/
1423 * BTRFS_SHARED_BLOCK_REF_KEY) then it holds the logical
1424 * bytenr of the parent block. Since new extents are always
1425 * created with indirect references, this will only be the case
1426 * when relocating a shared extent. In that case, root_objectid
1427 * will be BTRFS_TREE_RELOC_OBJECTID. Otherwise, parent must
1430 * @root_objectid: The id of the root where this modification has originated,
1431 * this can be either one of the well-known metadata trees or
1432 * the subvolume id which references this extent.
1434 * @owner: For data extents it is the inode number of the owning file.
1435 * For metadata extents this parameter holds the level in the
1436 * tree of the extent.
1438 * @offset: For metadata extents the offset is ignored and is currently
1439 * always passed as 0. For data extents it is the fileoffset
1440 * this extent belongs to.
1442 * @refs_to_add Number of references to add
1444 * @extent_op Pointer to a structure, holding information necessary when
1445 * updating a tree block's flags
1448 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
1449 struct btrfs_delayed_ref_node
*node
,
1450 u64 parent
, u64 root_objectid
,
1451 u64 owner
, u64 offset
, int refs_to_add
,
1452 struct btrfs_delayed_extent_op
*extent_op
)
1454 struct btrfs_path
*path
;
1455 struct extent_buffer
*leaf
;
1456 struct btrfs_extent_item
*item
;
1457 struct btrfs_key key
;
1458 u64 bytenr
= node
->bytenr
;
1459 u64 num_bytes
= node
->num_bytes
;
1463 path
= btrfs_alloc_path();
1467 /* this will setup the path even if it fails to insert the back ref */
1468 ret
= insert_inline_extent_backref(trans
, path
, bytenr
, num_bytes
,
1469 parent
, root_objectid
, owner
,
1470 offset
, refs_to_add
, extent_op
);
1471 if ((ret
< 0 && ret
!= -EAGAIN
) || !ret
)
1475 * Ok we had -EAGAIN which means we didn't have space to insert and
1476 * inline extent ref, so just update the reference count and add a
1479 leaf
= path
->nodes
[0];
1480 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
1481 item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
1482 refs
= btrfs_extent_refs(leaf
, item
);
1483 btrfs_set_extent_refs(leaf
, item
, refs
+ refs_to_add
);
1485 __run_delayed_extent_op(extent_op
, leaf
, item
);
1487 btrfs_mark_buffer_dirty(leaf
);
1488 btrfs_release_path(path
);
1490 /* now insert the actual backref */
1491 if (owner
< BTRFS_FIRST_FREE_OBJECTID
) {
1492 BUG_ON(refs_to_add
!= 1);
1493 ret
= insert_tree_block_ref(trans
, path
, bytenr
, parent
,
1496 ret
= insert_extent_data_ref(trans
, path
, bytenr
, parent
,
1497 root_objectid
, owner
, offset
,
1501 btrfs_abort_transaction(trans
, ret
);
1503 btrfs_free_path(path
);
1507 static int run_delayed_data_ref(struct btrfs_trans_handle
*trans
,
1508 struct btrfs_delayed_ref_node
*node
,
1509 struct btrfs_delayed_extent_op
*extent_op
,
1510 int insert_reserved
)
1513 struct btrfs_delayed_data_ref
*ref
;
1514 struct btrfs_key ins
;
1519 ins
.objectid
= node
->bytenr
;
1520 ins
.offset
= node
->num_bytes
;
1521 ins
.type
= BTRFS_EXTENT_ITEM_KEY
;
1523 ref
= btrfs_delayed_node_to_data_ref(node
);
1524 trace_run_delayed_data_ref(trans
->fs_info
, node
, ref
, node
->action
);
1526 if (node
->type
== BTRFS_SHARED_DATA_REF_KEY
)
1527 parent
= ref
->parent
;
1528 ref_root
= ref
->root
;
1530 if (node
->action
== BTRFS_ADD_DELAYED_REF
&& insert_reserved
) {
1532 flags
|= extent_op
->flags_to_set
;
1533 ret
= alloc_reserved_file_extent(trans
, parent
, ref_root
,
1534 flags
, ref
->objectid
,
1537 } else if (node
->action
== BTRFS_ADD_DELAYED_REF
) {
1538 ret
= __btrfs_inc_extent_ref(trans
, node
, parent
, ref_root
,
1539 ref
->objectid
, ref
->offset
,
1540 node
->ref_mod
, extent_op
);
1541 } else if (node
->action
== BTRFS_DROP_DELAYED_REF
) {
1542 ret
= __btrfs_free_extent(trans
, node
, parent
,
1543 ref_root
, ref
->objectid
,
1544 ref
->offset
, node
->ref_mod
,
1552 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op
*extent_op
,
1553 struct extent_buffer
*leaf
,
1554 struct btrfs_extent_item
*ei
)
1556 u64 flags
= btrfs_extent_flags(leaf
, ei
);
1557 if (extent_op
->update_flags
) {
1558 flags
|= extent_op
->flags_to_set
;
1559 btrfs_set_extent_flags(leaf
, ei
, flags
);
1562 if (extent_op
->update_key
) {
1563 struct btrfs_tree_block_info
*bi
;
1564 BUG_ON(!(flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
));
1565 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1566 btrfs_set_tree_block_key(leaf
, bi
, &extent_op
->key
);
1570 static int run_delayed_extent_op(struct btrfs_trans_handle
*trans
,
1571 struct btrfs_delayed_ref_head
*head
,
1572 struct btrfs_delayed_extent_op
*extent_op
)
1574 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
1575 struct btrfs_key key
;
1576 struct btrfs_path
*path
;
1577 struct btrfs_extent_item
*ei
;
1578 struct extent_buffer
*leaf
;
1582 int metadata
= !extent_op
->is_data
;
1584 if (TRANS_ABORTED(trans
))
1587 if (metadata
&& !btrfs_fs_incompat(fs_info
, SKINNY_METADATA
))
1590 path
= btrfs_alloc_path();
1594 key
.objectid
= head
->bytenr
;
1597 key
.type
= BTRFS_METADATA_ITEM_KEY
;
1598 key
.offset
= extent_op
->level
;
1600 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
1601 key
.offset
= head
->num_bytes
;
1605 ret
= btrfs_search_slot(trans
, fs_info
->extent_root
, &key
, path
, 0, 1);
1612 if (path
->slots
[0] > 0) {
1614 btrfs_item_key_to_cpu(path
->nodes
[0], &key
,
1616 if (key
.objectid
== head
->bytenr
&&
1617 key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
1618 key
.offset
== head
->num_bytes
)
1622 btrfs_release_path(path
);
1625 key
.objectid
= head
->bytenr
;
1626 key
.offset
= head
->num_bytes
;
1627 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
1636 leaf
= path
->nodes
[0];
1637 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
1639 if (unlikely(item_size
< sizeof(*ei
))) {
1641 btrfs_print_v0_err(fs_info
);
1642 btrfs_abort_transaction(trans
, err
);
1646 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
1647 __run_delayed_extent_op(extent_op
, leaf
, ei
);
1649 btrfs_mark_buffer_dirty(leaf
);
1651 btrfs_free_path(path
);
1655 static int run_delayed_tree_ref(struct btrfs_trans_handle
*trans
,
1656 struct btrfs_delayed_ref_node
*node
,
1657 struct btrfs_delayed_extent_op
*extent_op
,
1658 int insert_reserved
)
1661 struct btrfs_delayed_tree_ref
*ref
;
1665 ref
= btrfs_delayed_node_to_tree_ref(node
);
1666 trace_run_delayed_tree_ref(trans
->fs_info
, node
, ref
, node
->action
);
1668 if (node
->type
== BTRFS_SHARED_BLOCK_REF_KEY
)
1669 parent
= ref
->parent
;
1670 ref_root
= ref
->root
;
1672 if (node
->ref_mod
!= 1) {
1673 btrfs_err(trans
->fs_info
,
1674 "btree block(%llu) has %d references rather than 1: action %d ref_root %llu parent %llu",
1675 node
->bytenr
, node
->ref_mod
, node
->action
, ref_root
,
1679 if (node
->action
== BTRFS_ADD_DELAYED_REF
&& insert_reserved
) {
1680 BUG_ON(!extent_op
|| !extent_op
->update_flags
);
1681 ret
= alloc_reserved_tree_block(trans
, node
, extent_op
);
1682 } else if (node
->action
== BTRFS_ADD_DELAYED_REF
) {
1683 ret
= __btrfs_inc_extent_ref(trans
, node
, parent
, ref_root
,
1684 ref
->level
, 0, 1, extent_op
);
1685 } else if (node
->action
== BTRFS_DROP_DELAYED_REF
) {
1686 ret
= __btrfs_free_extent(trans
, node
, parent
, ref_root
,
1687 ref
->level
, 0, 1, extent_op
);
1694 /* helper function to actually process a single delayed ref entry */
1695 static int run_one_delayed_ref(struct btrfs_trans_handle
*trans
,
1696 struct btrfs_delayed_ref_node
*node
,
1697 struct btrfs_delayed_extent_op
*extent_op
,
1698 int insert_reserved
)
1702 if (TRANS_ABORTED(trans
)) {
1703 if (insert_reserved
)
1704 btrfs_pin_extent(trans
, node
->bytenr
, node
->num_bytes
, 1);
1708 if (node
->type
== BTRFS_TREE_BLOCK_REF_KEY
||
1709 node
->type
== BTRFS_SHARED_BLOCK_REF_KEY
)
1710 ret
= run_delayed_tree_ref(trans
, node
, extent_op
,
1712 else if (node
->type
== BTRFS_EXTENT_DATA_REF_KEY
||
1713 node
->type
== BTRFS_SHARED_DATA_REF_KEY
)
1714 ret
= run_delayed_data_ref(trans
, node
, extent_op
,
1718 if (ret
&& insert_reserved
)
1719 btrfs_pin_extent(trans
, node
->bytenr
, node
->num_bytes
, 1);
1723 static inline struct btrfs_delayed_ref_node
*
1724 select_delayed_ref(struct btrfs_delayed_ref_head
*head
)
1726 struct btrfs_delayed_ref_node
*ref
;
1728 if (RB_EMPTY_ROOT(&head
->ref_tree
.rb_root
))
1732 * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
1733 * This is to prevent a ref count from going down to zero, which deletes
1734 * the extent item from the extent tree, when there still are references
1735 * to add, which would fail because they would not find the extent item.
1737 if (!list_empty(&head
->ref_add_list
))
1738 return list_first_entry(&head
->ref_add_list
,
1739 struct btrfs_delayed_ref_node
, add_list
);
1741 ref
= rb_entry(rb_first_cached(&head
->ref_tree
),
1742 struct btrfs_delayed_ref_node
, ref_node
);
1743 ASSERT(list_empty(&ref
->add_list
));
1747 static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root
*delayed_refs
,
1748 struct btrfs_delayed_ref_head
*head
)
1750 spin_lock(&delayed_refs
->lock
);
1751 head
->processing
= 0;
1752 delayed_refs
->num_heads_ready
++;
1753 spin_unlock(&delayed_refs
->lock
);
1754 btrfs_delayed_ref_unlock(head
);
1757 static struct btrfs_delayed_extent_op
*cleanup_extent_op(
1758 struct btrfs_delayed_ref_head
*head
)
1760 struct btrfs_delayed_extent_op
*extent_op
= head
->extent_op
;
1765 if (head
->must_insert_reserved
) {
1766 head
->extent_op
= NULL
;
1767 btrfs_free_delayed_extent_op(extent_op
);
1773 static int run_and_cleanup_extent_op(struct btrfs_trans_handle
*trans
,
1774 struct btrfs_delayed_ref_head
*head
)
1776 struct btrfs_delayed_extent_op
*extent_op
;
1779 extent_op
= cleanup_extent_op(head
);
1782 head
->extent_op
= NULL
;
1783 spin_unlock(&head
->lock
);
1784 ret
= run_delayed_extent_op(trans
, head
, extent_op
);
1785 btrfs_free_delayed_extent_op(extent_op
);
1786 return ret
? ret
: 1;
1789 void btrfs_cleanup_ref_head_accounting(struct btrfs_fs_info
*fs_info
,
1790 struct btrfs_delayed_ref_root
*delayed_refs
,
1791 struct btrfs_delayed_ref_head
*head
)
1793 int nr_items
= 1; /* Dropping this ref head update. */
1796 * We had csum deletions accounted for in our delayed refs rsv, we need
1797 * to drop the csum leaves for this update from our delayed_refs_rsv.
1799 if (head
->total_ref_mod
< 0 && head
->is_data
) {
1800 spin_lock(&delayed_refs
->lock
);
1801 delayed_refs
->pending_csums
-= head
->num_bytes
;
1802 spin_unlock(&delayed_refs
->lock
);
1803 nr_items
+= btrfs_csum_bytes_to_leaves(fs_info
, head
->num_bytes
);
1806 btrfs_delayed_refs_rsv_release(fs_info
, nr_items
);
1809 static int cleanup_ref_head(struct btrfs_trans_handle
*trans
,
1810 struct btrfs_delayed_ref_head
*head
)
1813 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
1814 struct btrfs_delayed_ref_root
*delayed_refs
;
1817 delayed_refs
= &trans
->transaction
->delayed_refs
;
1819 ret
= run_and_cleanup_extent_op(trans
, head
);
1821 unselect_delayed_ref_head(delayed_refs
, head
);
1822 btrfs_debug(fs_info
, "run_delayed_extent_op returned %d", ret
);
1829 * Need to drop our head ref lock and re-acquire the delayed ref lock
1830 * and then re-check to make sure nobody got added.
1832 spin_unlock(&head
->lock
);
1833 spin_lock(&delayed_refs
->lock
);
1834 spin_lock(&head
->lock
);
1835 if (!RB_EMPTY_ROOT(&head
->ref_tree
.rb_root
) || head
->extent_op
) {
1836 spin_unlock(&head
->lock
);
1837 spin_unlock(&delayed_refs
->lock
);
1840 btrfs_delete_ref_head(delayed_refs
, head
);
1841 spin_unlock(&head
->lock
);
1842 spin_unlock(&delayed_refs
->lock
);
1844 if (head
->must_insert_reserved
) {
1845 btrfs_pin_extent(trans
, head
->bytenr
, head
->num_bytes
, 1);
1846 if (head
->is_data
) {
1847 ret
= btrfs_del_csums(trans
, fs_info
->csum_root
,
1848 head
->bytenr
, head
->num_bytes
);
1852 btrfs_cleanup_ref_head_accounting(fs_info
, delayed_refs
, head
);
1854 trace_run_delayed_ref_head(fs_info
, head
, 0);
1855 btrfs_delayed_ref_unlock(head
);
1856 btrfs_put_delayed_ref_head(head
);
1860 static struct btrfs_delayed_ref_head
*btrfs_obtain_ref_head(
1861 struct btrfs_trans_handle
*trans
)
1863 struct btrfs_delayed_ref_root
*delayed_refs
=
1864 &trans
->transaction
->delayed_refs
;
1865 struct btrfs_delayed_ref_head
*head
= NULL
;
1868 spin_lock(&delayed_refs
->lock
);
1869 head
= btrfs_select_ref_head(delayed_refs
);
1871 spin_unlock(&delayed_refs
->lock
);
1876 * Grab the lock that says we are going to process all the refs for
1879 ret
= btrfs_delayed_ref_lock(delayed_refs
, head
);
1880 spin_unlock(&delayed_refs
->lock
);
1883 * We may have dropped the spin lock to get the head mutex lock, and
1884 * that might have given someone else time to free the head. If that's
1885 * true, it has been removed from our list and we can move on.
1888 head
= ERR_PTR(-EAGAIN
);
1893 static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle
*trans
,
1894 struct btrfs_delayed_ref_head
*locked_ref
,
1895 unsigned long *run_refs
)
1897 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
1898 struct btrfs_delayed_ref_root
*delayed_refs
;
1899 struct btrfs_delayed_extent_op
*extent_op
;
1900 struct btrfs_delayed_ref_node
*ref
;
1901 int must_insert_reserved
= 0;
1904 delayed_refs
= &trans
->transaction
->delayed_refs
;
1906 lockdep_assert_held(&locked_ref
->mutex
);
1907 lockdep_assert_held(&locked_ref
->lock
);
1909 while ((ref
= select_delayed_ref(locked_ref
))) {
1911 btrfs_check_delayed_seq(fs_info
, ref
->seq
)) {
1912 spin_unlock(&locked_ref
->lock
);
1913 unselect_delayed_ref_head(delayed_refs
, locked_ref
);
1919 rb_erase_cached(&ref
->ref_node
, &locked_ref
->ref_tree
);
1920 RB_CLEAR_NODE(&ref
->ref_node
);
1921 if (!list_empty(&ref
->add_list
))
1922 list_del(&ref
->add_list
);
1924 * When we play the delayed ref, also correct the ref_mod on
1927 switch (ref
->action
) {
1928 case BTRFS_ADD_DELAYED_REF
:
1929 case BTRFS_ADD_DELAYED_EXTENT
:
1930 locked_ref
->ref_mod
-= ref
->ref_mod
;
1932 case BTRFS_DROP_DELAYED_REF
:
1933 locked_ref
->ref_mod
+= ref
->ref_mod
;
1938 atomic_dec(&delayed_refs
->num_entries
);
1941 * Record the must_insert_reserved flag before we drop the
1944 must_insert_reserved
= locked_ref
->must_insert_reserved
;
1945 locked_ref
->must_insert_reserved
= 0;
1947 extent_op
= locked_ref
->extent_op
;
1948 locked_ref
->extent_op
= NULL
;
1949 spin_unlock(&locked_ref
->lock
);
1951 ret
= run_one_delayed_ref(trans
, ref
, extent_op
,
1952 must_insert_reserved
);
1954 btrfs_free_delayed_extent_op(extent_op
);
1956 unselect_delayed_ref_head(delayed_refs
, locked_ref
);
1957 btrfs_put_delayed_ref(ref
);
1958 btrfs_debug(fs_info
, "run_one_delayed_ref returned %d",
1963 btrfs_put_delayed_ref(ref
);
1966 spin_lock(&locked_ref
->lock
);
1967 btrfs_merge_delayed_refs(trans
, delayed_refs
, locked_ref
);
1974 * Returns 0 on success or if called with an already aborted transaction.
1975 * Returns -ENOMEM or -EIO on failure and will abort the transaction.
1977 static noinline
int __btrfs_run_delayed_refs(struct btrfs_trans_handle
*trans
,
1980 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
1981 struct btrfs_delayed_ref_root
*delayed_refs
;
1982 struct btrfs_delayed_ref_head
*locked_ref
= NULL
;
1983 ktime_t start
= ktime_get();
1985 unsigned long count
= 0;
1986 unsigned long actual_count
= 0;
1988 delayed_refs
= &trans
->transaction
->delayed_refs
;
1991 locked_ref
= btrfs_obtain_ref_head(trans
);
1992 if (IS_ERR_OR_NULL(locked_ref
)) {
1993 if (PTR_ERR(locked_ref
) == -EAGAIN
) {
2002 * We need to try and merge add/drops of the same ref since we
2003 * can run into issues with relocate dropping the implicit ref
2004 * and then it being added back again before the drop can
2005 * finish. If we merged anything we need to re-loop so we can
2007 * Or we can get node references of the same type that weren't
2008 * merged when created due to bumps in the tree mod seq, and
2009 * we need to merge them to prevent adding an inline extent
2010 * backref before dropping it (triggering a BUG_ON at
2011 * insert_inline_extent_backref()).
2013 spin_lock(&locked_ref
->lock
);
2014 btrfs_merge_delayed_refs(trans
, delayed_refs
, locked_ref
);
2016 ret
= btrfs_run_delayed_refs_for_head(trans
, locked_ref
,
2018 if (ret
< 0 && ret
!= -EAGAIN
) {
2020 * Error, btrfs_run_delayed_refs_for_head already
2021 * unlocked everything so just bail out
2026 * Success, perform the usual cleanup of a processed
2029 ret
= cleanup_ref_head(trans
, locked_ref
);
2031 /* We dropped our lock, we need to loop. */
2040 * Either success case or btrfs_run_delayed_refs_for_head
2041 * returned -EAGAIN, meaning we need to select another head
2046 } while ((nr
!= -1 && count
< nr
) || locked_ref
);
2049 * We don't want to include ref heads since we can have empty ref heads
2050 * and those will drastically skew our runtime down since we just do
2051 * accounting, no actual extent tree updates.
2053 if (actual_count
> 0) {
2054 u64 runtime
= ktime_to_ns(ktime_sub(ktime_get(), start
));
2058 * We weigh the current average higher than our current runtime
2059 * to avoid large swings in the average.
2061 spin_lock(&delayed_refs
->lock
);
2062 avg
= fs_info
->avg_delayed_ref_runtime
* 3 + runtime
;
2063 fs_info
->avg_delayed_ref_runtime
= avg
>> 2; /* div by 4 */
2064 spin_unlock(&delayed_refs
->lock
);
2069 #ifdef SCRAMBLE_DELAYED_REFS
2071 * Normally delayed refs get processed in ascending bytenr order. This
2072 * correlates in most cases to the order added. To expose dependencies on this
2073 * order, we start to process the tree in the middle instead of the beginning
2075 static u64
find_middle(struct rb_root
*root
)
2077 struct rb_node
*n
= root
->rb_node
;
2078 struct btrfs_delayed_ref_node
*entry
;
2081 u64 first
= 0, last
= 0;
2085 entry
= rb_entry(n
, struct btrfs_delayed_ref_node
, rb_node
);
2086 first
= entry
->bytenr
;
2090 entry
= rb_entry(n
, struct btrfs_delayed_ref_node
, rb_node
);
2091 last
= entry
->bytenr
;
2096 entry
= rb_entry(n
, struct btrfs_delayed_ref_node
, rb_node
);
2097 WARN_ON(!entry
->in_tree
);
2099 middle
= entry
->bytenr
;
2113 * this starts processing the delayed reference count updates and
2114 * extent insertions we have queued up so far. count can be
2115 * 0, which means to process everything in the tree at the start
2116 * of the run (but not newly added entries), or it can be some target
2117 * number you'd like to process.
2119 * Returns 0 on success or if called with an aborted transaction
2120 * Returns <0 on error and aborts the transaction
2122 int btrfs_run_delayed_refs(struct btrfs_trans_handle
*trans
,
2123 unsigned long count
)
2125 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
2126 struct rb_node
*node
;
2127 struct btrfs_delayed_ref_root
*delayed_refs
;
2128 struct btrfs_delayed_ref_head
*head
;
2130 int run_all
= count
== (unsigned long)-1;
2132 /* We'll clean this up in btrfs_cleanup_transaction */
2133 if (TRANS_ABORTED(trans
))
2136 if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE
, &fs_info
->flags
))
2139 delayed_refs
= &trans
->transaction
->delayed_refs
;
2141 count
= delayed_refs
->num_heads_ready
;
2144 #ifdef SCRAMBLE_DELAYED_REFS
2145 delayed_refs
->run_delayed_start
= find_middle(&delayed_refs
->root
);
2147 ret
= __btrfs_run_delayed_refs(trans
, count
);
2149 btrfs_abort_transaction(trans
, ret
);
2154 btrfs_create_pending_block_groups(trans
);
2156 spin_lock(&delayed_refs
->lock
);
2157 node
= rb_first_cached(&delayed_refs
->href_root
);
2159 spin_unlock(&delayed_refs
->lock
);
2162 head
= rb_entry(node
, struct btrfs_delayed_ref_head
,
2164 refcount_inc(&head
->refs
);
2165 spin_unlock(&delayed_refs
->lock
);
2167 /* Mutex was contended, block until it's released and retry. */
2168 mutex_lock(&head
->mutex
);
2169 mutex_unlock(&head
->mutex
);
2171 btrfs_put_delayed_ref_head(head
);
2179 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle
*trans
,
2180 struct extent_buffer
*eb
, u64 flags
,
2181 int level
, int is_data
)
2183 struct btrfs_delayed_extent_op
*extent_op
;
2186 extent_op
= btrfs_alloc_delayed_extent_op();
2190 extent_op
->flags_to_set
= flags
;
2191 extent_op
->update_flags
= true;
2192 extent_op
->update_key
= false;
2193 extent_op
->is_data
= is_data
? true : false;
2194 extent_op
->level
= level
;
2196 ret
= btrfs_add_delayed_extent_op(trans
, eb
->start
, eb
->len
, extent_op
);
2198 btrfs_free_delayed_extent_op(extent_op
);
2202 static noinline
int check_delayed_ref(struct btrfs_root
*root
,
2203 struct btrfs_path
*path
,
2204 u64 objectid
, u64 offset
, u64 bytenr
)
2206 struct btrfs_delayed_ref_head
*head
;
2207 struct btrfs_delayed_ref_node
*ref
;
2208 struct btrfs_delayed_data_ref
*data_ref
;
2209 struct btrfs_delayed_ref_root
*delayed_refs
;
2210 struct btrfs_transaction
*cur_trans
;
2211 struct rb_node
*node
;
2214 spin_lock(&root
->fs_info
->trans_lock
);
2215 cur_trans
= root
->fs_info
->running_transaction
;
2217 refcount_inc(&cur_trans
->use_count
);
2218 spin_unlock(&root
->fs_info
->trans_lock
);
2222 delayed_refs
= &cur_trans
->delayed_refs
;
2223 spin_lock(&delayed_refs
->lock
);
2224 head
= btrfs_find_delayed_ref_head(delayed_refs
, bytenr
);
2226 spin_unlock(&delayed_refs
->lock
);
2227 btrfs_put_transaction(cur_trans
);
2231 if (!mutex_trylock(&head
->mutex
)) {
2232 refcount_inc(&head
->refs
);
2233 spin_unlock(&delayed_refs
->lock
);
2235 btrfs_release_path(path
);
2238 * Mutex was contended, block until it's released and let
2241 mutex_lock(&head
->mutex
);
2242 mutex_unlock(&head
->mutex
);
2243 btrfs_put_delayed_ref_head(head
);
2244 btrfs_put_transaction(cur_trans
);
2247 spin_unlock(&delayed_refs
->lock
);
2249 spin_lock(&head
->lock
);
2251 * XXX: We should replace this with a proper search function in the
2254 for (node
= rb_first_cached(&head
->ref_tree
); node
;
2255 node
= rb_next(node
)) {
2256 ref
= rb_entry(node
, struct btrfs_delayed_ref_node
, ref_node
);
2257 /* If it's a shared ref we know a cross reference exists */
2258 if (ref
->type
!= BTRFS_EXTENT_DATA_REF_KEY
) {
2263 data_ref
= btrfs_delayed_node_to_data_ref(ref
);
2266 * If our ref doesn't match the one we're currently looking at
2267 * then we have a cross reference.
2269 if (data_ref
->root
!= root
->root_key
.objectid
||
2270 data_ref
->objectid
!= objectid
||
2271 data_ref
->offset
!= offset
) {
2276 spin_unlock(&head
->lock
);
2277 mutex_unlock(&head
->mutex
);
2278 btrfs_put_transaction(cur_trans
);
2282 static noinline
int check_committed_ref(struct btrfs_root
*root
,
2283 struct btrfs_path
*path
,
2284 u64 objectid
, u64 offset
, u64 bytenr
,
2287 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
2288 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
2289 struct extent_buffer
*leaf
;
2290 struct btrfs_extent_data_ref
*ref
;
2291 struct btrfs_extent_inline_ref
*iref
;
2292 struct btrfs_extent_item
*ei
;
2293 struct btrfs_key key
;
2298 key
.objectid
= bytenr
;
2299 key
.offset
= (u64
)-1;
2300 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
2302 ret
= btrfs_search_slot(NULL
, extent_root
, &key
, path
, 0, 0);
2305 BUG_ON(ret
== 0); /* Corruption */
2308 if (path
->slots
[0] == 0)
2312 leaf
= path
->nodes
[0];
2313 btrfs_item_key_to_cpu(leaf
, &key
, path
->slots
[0]);
2315 if (key
.objectid
!= bytenr
|| key
.type
!= BTRFS_EXTENT_ITEM_KEY
)
2319 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
2320 ei
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_extent_item
);
2322 /* If extent item has more than 1 inline ref then it's shared */
2323 if (item_size
!= sizeof(*ei
) +
2324 btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY
))
2328 * If extent created before last snapshot => it's shared unless the
2329 * snapshot has been deleted. Use the heuristic if strict is false.
2332 (btrfs_extent_generation(leaf
, ei
) <=
2333 btrfs_root_last_snapshot(&root
->root_item
)))
2336 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
2338 /* If this extent has SHARED_DATA_REF then it's shared */
2339 type
= btrfs_get_extent_inline_ref_type(leaf
, iref
, BTRFS_REF_TYPE_DATA
);
2340 if (type
!= BTRFS_EXTENT_DATA_REF_KEY
)
2343 ref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
2344 if (btrfs_extent_refs(leaf
, ei
) !=
2345 btrfs_extent_data_ref_count(leaf
, ref
) ||
2346 btrfs_extent_data_ref_root(leaf
, ref
) !=
2347 root
->root_key
.objectid
||
2348 btrfs_extent_data_ref_objectid(leaf
, ref
) != objectid
||
2349 btrfs_extent_data_ref_offset(leaf
, ref
) != offset
)
2357 int btrfs_cross_ref_exist(struct btrfs_root
*root
, u64 objectid
, u64 offset
,
2358 u64 bytenr
, bool strict
)
2360 struct btrfs_path
*path
;
2363 path
= btrfs_alloc_path();
2368 ret
= check_committed_ref(root
, path
, objectid
,
2369 offset
, bytenr
, strict
);
2370 if (ret
&& ret
!= -ENOENT
)
2373 ret
= check_delayed_ref(root
, path
, objectid
, offset
, bytenr
);
2374 } while (ret
== -EAGAIN
);
2377 btrfs_free_path(path
);
2378 if (btrfs_is_data_reloc_root(root
))
2383 static int __btrfs_mod_ref(struct btrfs_trans_handle
*trans
,
2384 struct btrfs_root
*root
,
2385 struct extent_buffer
*buf
,
2386 int full_backref
, int inc
)
2388 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
2394 struct btrfs_key key
;
2395 struct btrfs_file_extent_item
*fi
;
2396 struct btrfs_ref generic_ref
= { 0 };
2397 bool for_reloc
= btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_RELOC
);
2403 if (btrfs_is_testing(fs_info
))
2406 ref_root
= btrfs_header_owner(buf
);
2407 nritems
= btrfs_header_nritems(buf
);
2408 level
= btrfs_header_level(buf
);
2410 if (!test_bit(BTRFS_ROOT_SHAREABLE
, &root
->state
) && level
== 0)
2414 parent
= buf
->start
;
2418 action
= BTRFS_ADD_DELAYED_REF
;
2420 action
= BTRFS_DROP_DELAYED_REF
;
2422 for (i
= 0; i
< nritems
; i
++) {
2424 btrfs_item_key_to_cpu(buf
, &key
, i
);
2425 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
2427 fi
= btrfs_item_ptr(buf
, i
,
2428 struct btrfs_file_extent_item
);
2429 if (btrfs_file_extent_type(buf
, fi
) ==
2430 BTRFS_FILE_EXTENT_INLINE
)
2432 bytenr
= btrfs_file_extent_disk_bytenr(buf
, fi
);
2436 num_bytes
= btrfs_file_extent_disk_num_bytes(buf
, fi
);
2437 key
.offset
-= btrfs_file_extent_offset(buf
, fi
);
2438 btrfs_init_generic_ref(&generic_ref
, action
, bytenr
,
2440 generic_ref
.real_root
= root
->root_key
.objectid
;
2441 btrfs_init_data_ref(&generic_ref
, ref_root
, key
.objectid
,
2442 key
.offset
, root
->root_key
.objectid
,
2444 generic_ref
.skip_qgroup
= for_reloc
;
2446 ret
= btrfs_inc_extent_ref(trans
, &generic_ref
);
2448 ret
= btrfs_free_extent(trans
, &generic_ref
);
2452 bytenr
= btrfs_node_blockptr(buf
, i
);
2453 num_bytes
= fs_info
->nodesize
;
2454 btrfs_init_generic_ref(&generic_ref
, action
, bytenr
,
2456 generic_ref
.real_root
= root
->root_key
.objectid
;
2457 btrfs_init_tree_ref(&generic_ref
, level
- 1, ref_root
,
2458 root
->root_key
.objectid
, for_reloc
);
2459 generic_ref
.skip_qgroup
= for_reloc
;
2461 ret
= btrfs_inc_extent_ref(trans
, &generic_ref
);
2463 ret
= btrfs_free_extent(trans
, &generic_ref
);
2473 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2474 struct extent_buffer
*buf
, int full_backref
)
2476 return __btrfs_mod_ref(trans
, root
, buf
, full_backref
, 1);
2479 int btrfs_dec_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2480 struct extent_buffer
*buf
, int full_backref
)
2482 return __btrfs_mod_ref(trans
, root
, buf
, full_backref
, 0);
2485 static u64
get_alloc_profile_by_root(struct btrfs_root
*root
, int data
)
2487 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
2492 flags
= BTRFS_BLOCK_GROUP_DATA
;
2493 else if (root
== fs_info
->chunk_root
)
2494 flags
= BTRFS_BLOCK_GROUP_SYSTEM
;
2496 flags
= BTRFS_BLOCK_GROUP_METADATA
;
2498 ret
= btrfs_get_alloc_profile(fs_info
, flags
);
2502 static u64
first_logical_byte(struct btrfs_fs_info
*fs_info
, u64 search_start
)
2504 struct btrfs_block_group
*cache
;
2507 spin_lock(&fs_info
->block_group_cache_lock
);
2508 bytenr
= fs_info
->first_logical_byte
;
2509 spin_unlock(&fs_info
->block_group_cache_lock
);
2511 if (bytenr
< (u64
)-1)
2514 cache
= btrfs_lookup_first_block_group(fs_info
, search_start
);
2518 bytenr
= cache
->start
;
2519 btrfs_put_block_group(cache
);
2524 static int pin_down_extent(struct btrfs_trans_handle
*trans
,
2525 struct btrfs_block_group
*cache
,
2526 u64 bytenr
, u64 num_bytes
, int reserved
)
2528 struct btrfs_fs_info
*fs_info
= cache
->fs_info
;
2530 spin_lock(&cache
->space_info
->lock
);
2531 spin_lock(&cache
->lock
);
2532 cache
->pinned
+= num_bytes
;
2533 btrfs_space_info_update_bytes_pinned(fs_info
, cache
->space_info
,
2536 cache
->reserved
-= num_bytes
;
2537 cache
->space_info
->bytes_reserved
-= num_bytes
;
2539 spin_unlock(&cache
->lock
);
2540 spin_unlock(&cache
->space_info
->lock
);
2542 set_extent_dirty(&trans
->transaction
->pinned_extents
, bytenr
,
2543 bytenr
+ num_bytes
- 1, GFP_NOFS
| __GFP_NOFAIL
);
2547 int btrfs_pin_extent(struct btrfs_trans_handle
*trans
,
2548 u64 bytenr
, u64 num_bytes
, int reserved
)
2550 struct btrfs_block_group
*cache
;
2552 cache
= btrfs_lookup_block_group(trans
->fs_info
, bytenr
);
2553 BUG_ON(!cache
); /* Logic error */
2555 pin_down_extent(trans
, cache
, bytenr
, num_bytes
, reserved
);
2557 btrfs_put_block_group(cache
);
2562 * this function must be called within transaction
2564 int btrfs_pin_extent_for_log_replay(struct btrfs_trans_handle
*trans
,
2565 u64 bytenr
, u64 num_bytes
)
2567 struct btrfs_block_group
*cache
;
2570 cache
= btrfs_lookup_block_group(trans
->fs_info
, bytenr
);
2575 * pull in the free space cache (if any) so that our pin
2576 * removes the free space from the cache. We have load_only set
2577 * to one because the slow code to read in the free extents does check
2578 * the pinned extents.
2580 btrfs_cache_block_group(cache
, 1);
2582 * Make sure we wait until the cache is completely built in case it is
2583 * missing or is invalid and therefore needs to be rebuilt.
2585 ret
= btrfs_wait_block_group_cache_done(cache
);
2589 pin_down_extent(trans
, cache
, bytenr
, num_bytes
, 0);
2591 /* remove us from the free space cache (if we're there at all) */
2592 ret
= btrfs_remove_free_space(cache
, bytenr
, num_bytes
);
2594 btrfs_put_block_group(cache
);
2598 static int __exclude_logged_extent(struct btrfs_fs_info
*fs_info
,
2599 u64 start
, u64 num_bytes
)
2602 struct btrfs_block_group
*block_group
;
2604 block_group
= btrfs_lookup_block_group(fs_info
, start
);
2608 btrfs_cache_block_group(block_group
, 1);
2610 * Make sure we wait until the cache is completely built in case it is
2611 * missing or is invalid and therefore needs to be rebuilt.
2613 ret
= btrfs_wait_block_group_cache_done(block_group
);
2617 ret
= btrfs_remove_free_space(block_group
, start
, num_bytes
);
2619 btrfs_put_block_group(block_group
);
2623 int btrfs_exclude_logged_extents(struct extent_buffer
*eb
)
2625 struct btrfs_fs_info
*fs_info
= eb
->fs_info
;
2626 struct btrfs_file_extent_item
*item
;
2627 struct btrfs_key key
;
2632 if (!btrfs_fs_incompat(fs_info
, MIXED_GROUPS
))
2635 for (i
= 0; i
< btrfs_header_nritems(eb
); i
++) {
2636 btrfs_item_key_to_cpu(eb
, &key
, i
);
2637 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
2639 item
= btrfs_item_ptr(eb
, i
, struct btrfs_file_extent_item
);
2640 found_type
= btrfs_file_extent_type(eb
, item
);
2641 if (found_type
== BTRFS_FILE_EXTENT_INLINE
)
2643 if (btrfs_file_extent_disk_bytenr(eb
, item
) == 0)
2645 key
.objectid
= btrfs_file_extent_disk_bytenr(eb
, item
);
2646 key
.offset
= btrfs_file_extent_disk_num_bytes(eb
, item
);
2647 ret
= __exclude_logged_extent(fs_info
, key
.objectid
, key
.offset
);
2656 btrfs_inc_block_group_reservations(struct btrfs_block_group
*bg
)
2658 atomic_inc(&bg
->reservations
);
2662 * Returns the free cluster for the given space info and sets empty_cluster to
2663 * what it should be based on the mount options.
2665 static struct btrfs_free_cluster
*
2666 fetch_cluster_info(struct btrfs_fs_info
*fs_info
,
2667 struct btrfs_space_info
*space_info
, u64
*empty_cluster
)
2669 struct btrfs_free_cluster
*ret
= NULL
;
2672 if (btrfs_mixed_space_info(space_info
))
2675 if (space_info
->flags
& BTRFS_BLOCK_GROUP_METADATA
) {
2676 ret
= &fs_info
->meta_alloc_cluster
;
2677 if (btrfs_test_opt(fs_info
, SSD
))
2678 *empty_cluster
= SZ_2M
;
2680 *empty_cluster
= SZ_64K
;
2681 } else if ((space_info
->flags
& BTRFS_BLOCK_GROUP_DATA
) &&
2682 btrfs_test_opt(fs_info
, SSD_SPREAD
)) {
2683 *empty_cluster
= SZ_2M
;
2684 ret
= &fs_info
->data_alloc_cluster
;
2690 static int unpin_extent_range(struct btrfs_fs_info
*fs_info
,
2692 const bool return_free_space
)
2694 struct btrfs_block_group
*cache
= NULL
;
2695 struct btrfs_space_info
*space_info
;
2696 struct btrfs_block_rsv
*global_rsv
= &fs_info
->global_block_rsv
;
2697 struct btrfs_free_cluster
*cluster
= NULL
;
2699 u64 total_unpinned
= 0;
2700 u64 empty_cluster
= 0;
2703 while (start
<= end
) {
2706 start
>= cache
->start
+ cache
->length
) {
2708 btrfs_put_block_group(cache
);
2710 cache
= btrfs_lookup_block_group(fs_info
, start
);
2711 BUG_ON(!cache
); /* Logic error */
2713 cluster
= fetch_cluster_info(fs_info
,
2716 empty_cluster
<<= 1;
2719 len
= cache
->start
+ cache
->length
- start
;
2720 len
= min(len
, end
+ 1 - start
);
2722 down_read(&fs_info
->commit_root_sem
);
2723 if (start
< cache
->last_byte_to_unpin
&& return_free_space
) {
2724 u64 add_len
= min(len
, cache
->last_byte_to_unpin
- start
);
2726 btrfs_add_free_space(cache
, start
, add_len
);
2728 up_read(&fs_info
->commit_root_sem
);
2731 total_unpinned
+= len
;
2732 space_info
= cache
->space_info
;
2735 * If this space cluster has been marked as fragmented and we've
2736 * unpinned enough in this block group to potentially allow a
2737 * cluster to be created inside of it go ahead and clear the
2740 if (cluster
&& cluster
->fragmented
&&
2741 total_unpinned
> empty_cluster
) {
2742 spin_lock(&cluster
->lock
);
2743 cluster
->fragmented
= 0;
2744 spin_unlock(&cluster
->lock
);
2747 spin_lock(&space_info
->lock
);
2748 spin_lock(&cache
->lock
);
2749 cache
->pinned
-= len
;
2750 btrfs_space_info_update_bytes_pinned(fs_info
, space_info
, -len
);
2751 space_info
->max_extent_size
= 0;
2753 space_info
->bytes_readonly
+= len
;
2755 } else if (btrfs_is_zoned(fs_info
)) {
2756 /* Need reset before reusing in a zoned block group */
2757 space_info
->bytes_zone_unusable
+= len
;
2760 spin_unlock(&cache
->lock
);
2761 if (!readonly
&& return_free_space
&&
2762 global_rsv
->space_info
== space_info
) {
2765 spin_lock(&global_rsv
->lock
);
2766 if (!global_rsv
->full
) {
2767 to_add
= min(len
, global_rsv
->size
-
2768 global_rsv
->reserved
);
2769 global_rsv
->reserved
+= to_add
;
2770 btrfs_space_info_update_bytes_may_use(fs_info
,
2771 space_info
, to_add
);
2772 if (global_rsv
->reserved
>= global_rsv
->size
)
2773 global_rsv
->full
= 1;
2776 spin_unlock(&global_rsv
->lock
);
2778 /* Add to any tickets we may have */
2779 if (!readonly
&& return_free_space
&& len
)
2780 btrfs_try_granting_tickets(fs_info
, space_info
);
2781 spin_unlock(&space_info
->lock
);
2785 btrfs_put_block_group(cache
);
2789 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
)
2791 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
2792 struct btrfs_block_group
*block_group
, *tmp
;
2793 struct list_head
*deleted_bgs
;
2794 struct extent_io_tree
*unpin
;
2799 unpin
= &trans
->transaction
->pinned_extents
;
2801 while (!TRANS_ABORTED(trans
)) {
2802 struct extent_state
*cached_state
= NULL
;
2804 mutex_lock(&fs_info
->unused_bg_unpin_mutex
);
2805 ret
= find_first_extent_bit(unpin
, 0, &start
, &end
,
2806 EXTENT_DIRTY
, &cached_state
);
2808 mutex_unlock(&fs_info
->unused_bg_unpin_mutex
);
2812 if (btrfs_test_opt(fs_info
, DISCARD_SYNC
))
2813 ret
= btrfs_discard_extent(fs_info
, start
,
2814 end
+ 1 - start
, NULL
);
2816 clear_extent_dirty(unpin
, start
, end
, &cached_state
);
2817 unpin_extent_range(fs_info
, start
, end
, true);
2818 mutex_unlock(&fs_info
->unused_bg_unpin_mutex
);
2819 free_extent_state(cached_state
);
2823 if (btrfs_test_opt(fs_info
, DISCARD_ASYNC
)) {
2824 btrfs_discard_calc_delay(&fs_info
->discard_ctl
);
2825 btrfs_discard_schedule_work(&fs_info
->discard_ctl
, true);
2829 * Transaction is finished. We don't need the lock anymore. We
2830 * do need to clean up the block groups in case of a transaction
2833 deleted_bgs
= &trans
->transaction
->deleted_bgs
;
2834 list_for_each_entry_safe(block_group
, tmp
, deleted_bgs
, bg_list
) {
2838 if (!TRANS_ABORTED(trans
))
2839 ret
= btrfs_discard_extent(fs_info
,
2841 block_group
->length
,
2844 list_del_init(&block_group
->bg_list
);
2845 btrfs_unfreeze_block_group(block_group
);
2846 btrfs_put_block_group(block_group
);
2849 const char *errstr
= btrfs_decode_error(ret
);
2851 "discard failed while removing blockgroup: errno=%d %s",
2860 * Drop one or more refs of @node.
2862 * 1. Locate the extent refs.
2863 * It's either inline in EXTENT/METADATA_ITEM or in keyed SHARED_* item.
2864 * Locate it, then reduce the refs number or remove the ref line completely.
2866 * 2. Update the refs count in EXTENT/METADATA_ITEM
2868 * Inline backref case:
2870 * in extent tree we have:
2872 * item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
2873 * refs 2 gen 6 flags DATA
2874 * extent data backref root FS_TREE objectid 258 offset 0 count 1
2875 * extent data backref root FS_TREE objectid 257 offset 0 count 1
2877 * This function gets called with:
2879 * node->bytenr = 13631488
2880 * node->num_bytes = 1048576
2881 * root_objectid = FS_TREE
2882 * owner_objectid = 257
2886 * Then we should get some like:
2888 * item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
2889 * refs 1 gen 6 flags DATA
2890 * extent data backref root FS_TREE objectid 258 offset 0 count 1
2892 * Keyed backref case:
2894 * in extent tree we have:
2896 * item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
2897 * refs 754 gen 6 flags DATA
2899 * item 2 key (13631488 EXTENT_DATA_REF <HASH>) itemoff 3915 itemsize 28
2900 * extent data backref root FS_TREE objectid 866 offset 0 count 1
2902 * This function get called with:
2904 * node->bytenr = 13631488
2905 * node->num_bytes = 1048576
2906 * root_objectid = FS_TREE
2907 * owner_objectid = 866
2911 * Then we should get some like:
2913 * item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
2914 * refs 753 gen 6 flags DATA
2916 * And that (13631488 EXTENT_DATA_REF <HASH>) gets removed.
2918 static int __btrfs_free_extent(struct btrfs_trans_handle
*trans
,
2919 struct btrfs_delayed_ref_node
*node
, u64 parent
,
2920 u64 root_objectid
, u64 owner_objectid
,
2921 u64 owner_offset
, int refs_to_drop
,
2922 struct btrfs_delayed_extent_op
*extent_op
)
2924 struct btrfs_fs_info
*info
= trans
->fs_info
;
2925 struct btrfs_key key
;
2926 struct btrfs_path
*path
;
2927 struct btrfs_root
*extent_root
= info
->extent_root
;
2928 struct extent_buffer
*leaf
;
2929 struct btrfs_extent_item
*ei
;
2930 struct btrfs_extent_inline_ref
*iref
;
2933 int extent_slot
= 0;
2934 int found_extent
= 0;
2938 u64 bytenr
= node
->bytenr
;
2939 u64 num_bytes
= node
->num_bytes
;
2941 bool skinny_metadata
= btrfs_fs_incompat(info
, SKINNY_METADATA
);
2943 path
= btrfs_alloc_path();
2947 is_data
= owner_objectid
>= BTRFS_FIRST_FREE_OBJECTID
;
2949 if (!is_data
&& refs_to_drop
!= 1) {
2951 "invalid refs_to_drop, dropping more than 1 refs for tree block %llu refs_to_drop %u",
2952 node
->bytenr
, refs_to_drop
);
2954 btrfs_abort_transaction(trans
, ret
);
2959 skinny_metadata
= false;
2961 ret
= lookup_extent_backref(trans
, path
, &iref
, bytenr
, num_bytes
,
2962 parent
, root_objectid
, owner_objectid
,
2966 * Either the inline backref or the SHARED_DATA_REF/
2967 * SHARED_BLOCK_REF is found
2969 * Here is a quick path to locate EXTENT/METADATA_ITEM.
2970 * It's possible the EXTENT/METADATA_ITEM is near current slot.
2972 extent_slot
= path
->slots
[0];
2973 while (extent_slot
>= 0) {
2974 btrfs_item_key_to_cpu(path
->nodes
[0], &key
,
2976 if (key
.objectid
!= bytenr
)
2978 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
2979 key
.offset
== num_bytes
) {
2983 if (key
.type
== BTRFS_METADATA_ITEM_KEY
&&
2984 key
.offset
== owner_objectid
) {
2989 /* Quick path didn't find the EXTEMT/METADATA_ITEM */
2990 if (path
->slots
[0] - extent_slot
> 5)
2995 if (!found_extent
) {
2998 "invalid iref, no EXTENT/METADATA_ITEM found but has inline extent ref");
2999 btrfs_abort_transaction(trans
, -EUCLEAN
);
3002 /* Must be SHARED_* item, remove the backref first */
3003 ret
= remove_extent_backref(trans
, path
, NULL
,
3005 is_data
, &last_ref
);
3007 btrfs_abort_transaction(trans
, ret
);
3010 btrfs_release_path(path
);
3012 /* Slow path to locate EXTENT/METADATA_ITEM */
3013 key
.objectid
= bytenr
;
3014 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3015 key
.offset
= num_bytes
;
3017 if (!is_data
&& skinny_metadata
) {
3018 key
.type
= BTRFS_METADATA_ITEM_KEY
;
3019 key
.offset
= owner_objectid
;
3022 ret
= btrfs_search_slot(trans
, extent_root
,
3024 if (ret
> 0 && skinny_metadata
&& path
->slots
[0]) {
3026 * Couldn't find our skinny metadata item,
3027 * see if we have ye olde extent item.
3030 btrfs_item_key_to_cpu(path
->nodes
[0], &key
,
3032 if (key
.objectid
== bytenr
&&
3033 key
.type
== BTRFS_EXTENT_ITEM_KEY
&&
3034 key
.offset
== num_bytes
)
3038 if (ret
> 0 && skinny_metadata
) {
3039 skinny_metadata
= false;
3040 key
.objectid
= bytenr
;
3041 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
3042 key
.offset
= num_bytes
;
3043 btrfs_release_path(path
);
3044 ret
= btrfs_search_slot(trans
, extent_root
,
3050 "umm, got %d back from search, was looking for %llu",
3053 btrfs_print_leaf(path
->nodes
[0]);
3056 btrfs_abort_transaction(trans
, ret
);
3059 extent_slot
= path
->slots
[0];
3061 } else if (WARN_ON(ret
== -ENOENT
)) {
3062 btrfs_print_leaf(path
->nodes
[0]);
3064 "unable to find ref byte nr %llu parent %llu root %llu owner %llu offset %llu",
3065 bytenr
, parent
, root_objectid
, owner_objectid
,
3067 btrfs_abort_transaction(trans
, ret
);
3070 btrfs_abort_transaction(trans
, ret
);
3074 leaf
= path
->nodes
[0];
3075 item_size
= btrfs_item_size_nr(leaf
, extent_slot
);
3076 if (unlikely(item_size
< sizeof(*ei
))) {
3078 btrfs_print_v0_err(info
);
3079 btrfs_abort_transaction(trans
, ret
);
3082 ei
= btrfs_item_ptr(leaf
, extent_slot
,
3083 struct btrfs_extent_item
);
3084 if (owner_objectid
< BTRFS_FIRST_FREE_OBJECTID
&&
3085 key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
3086 struct btrfs_tree_block_info
*bi
;
3087 if (item_size
< sizeof(*ei
) + sizeof(*bi
)) {
3089 "invalid extent item size for key (%llu, %u, %llu) owner %llu, has %u expect >= %zu",
3090 key
.objectid
, key
.type
, key
.offset
,
3091 owner_objectid
, item_size
,
3092 sizeof(*ei
) + sizeof(*bi
));
3093 btrfs_abort_transaction(trans
, -EUCLEAN
);
3096 bi
= (struct btrfs_tree_block_info
*)(ei
+ 1);
3097 WARN_ON(owner_objectid
!= btrfs_tree_block_level(leaf
, bi
));
3100 refs
= btrfs_extent_refs(leaf
, ei
);
3101 if (refs
< refs_to_drop
) {
3103 "trying to drop %d refs but we only have %llu for bytenr %llu",
3104 refs_to_drop
, refs
, bytenr
);
3105 btrfs_abort_transaction(trans
, -EUCLEAN
);
3108 refs
-= refs_to_drop
;
3112 __run_delayed_extent_op(extent_op
, leaf
, ei
);
3114 * In the case of inline back ref, reference count will
3115 * be updated by remove_extent_backref
3118 if (!found_extent
) {
3120 "invalid iref, got inlined extent ref but no EXTENT/METADATA_ITEM found");
3121 btrfs_abort_transaction(trans
, -EUCLEAN
);
3125 btrfs_set_extent_refs(leaf
, ei
, refs
);
3126 btrfs_mark_buffer_dirty(leaf
);
3129 ret
= remove_extent_backref(trans
, path
, iref
,
3130 refs_to_drop
, is_data
,
3133 btrfs_abort_transaction(trans
, ret
);
3138 /* In this branch refs == 1 */
3140 if (is_data
&& refs_to_drop
!=
3141 extent_data_ref_count(path
, iref
)) {
3143 "invalid refs_to_drop, current refs %u refs_to_drop %u",
3144 extent_data_ref_count(path
, iref
),
3146 btrfs_abort_transaction(trans
, -EUCLEAN
);
3150 if (path
->slots
[0] != extent_slot
) {
3152 "invalid iref, extent item key (%llu %u %llu) doesn't have wanted iref",
3153 key
.objectid
, key
.type
,
3155 btrfs_abort_transaction(trans
, -EUCLEAN
);
3160 * No inline ref, we must be at SHARED_* item,
3161 * And it's single ref, it must be:
3162 * | extent_slot ||extent_slot + 1|
3163 * [ EXTENT/METADATA_ITEM ][ SHARED_* ITEM ]
3165 if (path
->slots
[0] != extent_slot
+ 1) {
3167 "invalid SHARED_* item, previous item is not EXTENT/METADATA_ITEM");
3168 btrfs_abort_transaction(trans
, -EUCLEAN
);
3171 path
->slots
[0] = extent_slot
;
3177 ret
= btrfs_del_items(trans
, extent_root
, path
, path
->slots
[0],
3180 btrfs_abort_transaction(trans
, ret
);
3183 btrfs_release_path(path
);
3186 ret
= btrfs_del_csums(trans
, info
->csum_root
, bytenr
,
3189 btrfs_abort_transaction(trans
, ret
);
3194 ret
= add_to_free_space_tree(trans
, bytenr
, num_bytes
);
3196 btrfs_abort_transaction(trans
, ret
);
3200 ret
= btrfs_update_block_group(trans
, bytenr
, num_bytes
, 0);
3202 btrfs_abort_transaction(trans
, ret
);
3206 btrfs_release_path(path
);
3209 btrfs_free_path(path
);
3213 * Leaf dump can take up a lot of log buffer, so we only do full leaf
3214 * dump for debug build.
3216 if (IS_ENABLED(CONFIG_BTRFS_DEBUG
)) {
3217 btrfs_crit(info
, "path->slots[0]=%d extent_slot=%d",
3218 path
->slots
[0], extent_slot
);
3219 btrfs_print_leaf(path
->nodes
[0]);
3222 btrfs_free_path(path
);
3227 * when we free an block, it is possible (and likely) that we free the last
3228 * delayed ref for that extent as well. This searches the delayed ref tree for
3229 * a given extent, and if there are no other delayed refs to be processed, it
3230 * removes it from the tree.
3232 static noinline
int check_ref_cleanup(struct btrfs_trans_handle
*trans
,
3235 struct btrfs_delayed_ref_head
*head
;
3236 struct btrfs_delayed_ref_root
*delayed_refs
;
3239 delayed_refs
= &trans
->transaction
->delayed_refs
;
3240 spin_lock(&delayed_refs
->lock
);
3241 head
= btrfs_find_delayed_ref_head(delayed_refs
, bytenr
);
3243 goto out_delayed_unlock
;
3245 spin_lock(&head
->lock
);
3246 if (!RB_EMPTY_ROOT(&head
->ref_tree
.rb_root
))
3249 if (cleanup_extent_op(head
) != NULL
)
3253 * waiting for the lock here would deadlock. If someone else has it
3254 * locked they are already in the process of dropping it anyway
3256 if (!mutex_trylock(&head
->mutex
))
3259 btrfs_delete_ref_head(delayed_refs
, head
);
3260 head
->processing
= 0;
3262 spin_unlock(&head
->lock
);
3263 spin_unlock(&delayed_refs
->lock
);
3265 BUG_ON(head
->extent_op
);
3266 if (head
->must_insert_reserved
)
3269 btrfs_cleanup_ref_head_accounting(trans
->fs_info
, delayed_refs
, head
);
3270 mutex_unlock(&head
->mutex
);
3271 btrfs_put_delayed_ref_head(head
);
3274 spin_unlock(&head
->lock
);
3277 spin_unlock(&delayed_refs
->lock
);
3281 void btrfs_free_tree_block(struct btrfs_trans_handle
*trans
,
3283 struct extent_buffer
*buf
,
3284 u64 parent
, int last_ref
)
3286 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
3287 struct btrfs_ref generic_ref
= { 0 };
3290 btrfs_init_generic_ref(&generic_ref
, BTRFS_DROP_DELAYED_REF
,
3291 buf
->start
, buf
->len
, parent
);
3292 btrfs_init_tree_ref(&generic_ref
, btrfs_header_level(buf
),
3295 if (root_id
!= BTRFS_TREE_LOG_OBJECTID
) {
3296 btrfs_ref_tree_mod(fs_info
, &generic_ref
);
3297 ret
= btrfs_add_delayed_tree_ref(trans
, &generic_ref
, NULL
);
3298 BUG_ON(ret
); /* -ENOMEM */
3301 if (last_ref
&& btrfs_header_generation(buf
) == trans
->transid
) {
3302 struct btrfs_block_group
*cache
;
3303 bool must_pin
= false;
3305 if (root_id
!= BTRFS_TREE_LOG_OBJECTID
) {
3306 ret
= check_ref_cleanup(trans
, buf
->start
);
3308 btrfs_redirty_list_add(trans
->transaction
, buf
);
3313 cache
= btrfs_lookup_block_group(fs_info
, buf
->start
);
3315 if (btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_WRITTEN
)) {
3316 pin_down_extent(trans
, cache
, buf
->start
, buf
->len
, 1);
3317 btrfs_put_block_group(cache
);
3322 * If this is a leaf and there are tree mod log users, we may
3323 * have recorded mod log operations that point to this leaf.
3324 * So we must make sure no one reuses this leaf's extent before
3325 * mod log operations are applied to a node, otherwise after
3326 * rewinding a node using the mod log operations we get an
3327 * inconsistent btree, as the leaf's extent may now be used as
3328 * a node or leaf for another different btree.
3329 * We are safe from races here because at this point no other
3330 * node or root points to this extent buffer, so if after this
3331 * check a new tree mod log user joins, it will not be able to
3332 * find a node pointing to this leaf and record operations that
3333 * point to this leaf.
3335 if (btrfs_header_level(buf
) == 0 &&
3336 test_bit(BTRFS_FS_TREE_MOD_LOG_USERS
, &fs_info
->flags
))
3339 if (must_pin
|| btrfs_is_zoned(fs_info
)) {
3340 btrfs_redirty_list_add(trans
->transaction
, buf
);
3341 pin_down_extent(trans
, cache
, buf
->start
, buf
->len
, 1);
3342 btrfs_put_block_group(cache
);
3346 WARN_ON(test_bit(EXTENT_BUFFER_DIRTY
, &buf
->bflags
));
3348 btrfs_add_free_space(cache
, buf
->start
, buf
->len
);
3349 btrfs_free_reserved_bytes(cache
, buf
->len
, 0);
3350 btrfs_put_block_group(cache
);
3351 trace_btrfs_reserved_extent_free(fs_info
, buf
->start
, buf
->len
);
3356 * Deleting the buffer, clear the corrupt flag since it doesn't
3359 clear_bit(EXTENT_BUFFER_CORRUPT
, &buf
->bflags
);
3363 /* Can return -ENOMEM */
3364 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_ref
*ref
)
3366 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
3369 if (btrfs_is_testing(fs_info
))
3373 * tree log blocks never actually go into the extent allocation
3374 * tree, just update pinning info and exit early.
3376 if ((ref
->type
== BTRFS_REF_METADATA
&&
3377 ref
->tree_ref
.root
== BTRFS_TREE_LOG_OBJECTID
) ||
3378 (ref
->type
== BTRFS_REF_DATA
&&
3379 ref
->data_ref
.ref_root
== BTRFS_TREE_LOG_OBJECTID
)) {
3380 /* unlocks the pinned mutex */
3381 btrfs_pin_extent(trans
, ref
->bytenr
, ref
->len
, 1);
3383 } else if (ref
->type
== BTRFS_REF_METADATA
) {
3384 ret
= btrfs_add_delayed_tree_ref(trans
, ref
, NULL
);
3386 ret
= btrfs_add_delayed_data_ref(trans
, ref
, 0);
3389 if (!((ref
->type
== BTRFS_REF_METADATA
&&
3390 ref
->tree_ref
.root
== BTRFS_TREE_LOG_OBJECTID
) ||
3391 (ref
->type
== BTRFS_REF_DATA
&&
3392 ref
->data_ref
.ref_root
== BTRFS_TREE_LOG_OBJECTID
)))
3393 btrfs_ref_tree_mod(fs_info
, ref
);
3398 enum btrfs_loop_type
{
3399 LOOP_CACHING_NOWAIT
,
3406 btrfs_lock_block_group(struct btrfs_block_group
*cache
,
3410 down_read(&cache
->data_rwsem
);
3413 static inline void btrfs_grab_block_group(struct btrfs_block_group
*cache
,
3416 btrfs_get_block_group(cache
);
3418 down_read(&cache
->data_rwsem
);
3421 static struct btrfs_block_group
*btrfs_lock_cluster(
3422 struct btrfs_block_group
*block_group
,
3423 struct btrfs_free_cluster
*cluster
,
3425 __acquires(&cluster
->refill_lock
)
3427 struct btrfs_block_group
*used_bg
= NULL
;
3429 spin_lock(&cluster
->refill_lock
);
3431 used_bg
= cluster
->block_group
;
3435 if (used_bg
== block_group
)
3438 btrfs_get_block_group(used_bg
);
3443 if (down_read_trylock(&used_bg
->data_rwsem
))
3446 spin_unlock(&cluster
->refill_lock
);
3448 /* We should only have one-level nested. */
3449 down_read_nested(&used_bg
->data_rwsem
, SINGLE_DEPTH_NESTING
);
3451 spin_lock(&cluster
->refill_lock
);
3452 if (used_bg
== cluster
->block_group
)
3455 up_read(&used_bg
->data_rwsem
);
3456 btrfs_put_block_group(used_bg
);
3461 btrfs_release_block_group(struct btrfs_block_group
*cache
,
3465 up_read(&cache
->data_rwsem
);
3466 btrfs_put_block_group(cache
);
3469 enum btrfs_extent_allocation_policy
{
3470 BTRFS_EXTENT_ALLOC_CLUSTERED
,
3471 BTRFS_EXTENT_ALLOC_ZONED
,
3475 * Structure used internally for find_free_extent() function. Wraps needed
3478 struct find_free_extent_ctl
{
3479 /* Basic allocation info */
3485 /* Where to start the search inside the bg */
3488 /* For clustered allocation */
3490 struct btrfs_free_cluster
*last_ptr
;
3493 bool have_caching_bg
;
3494 bool orig_have_caching_bg
;
3496 /* Allocation is called for tree-log */
3499 /* Allocation is called for data relocation */
3500 bool for_data_reloc
;
3502 /* RAID index, converted from flags */
3506 * Current loop number, check find_free_extent_update_loop() for details
3511 * Whether we're refilling a cluster, if true we need to re-search
3512 * current block group but don't try to refill the cluster again.
3514 bool retry_clustered
;
3517 * Whether we're updating free space cache, if true we need to re-search
3518 * current block group but don't try updating free space cache again.
3520 bool retry_unclustered
;
3522 /* If current block group is cached */
3525 /* Max contiguous hole found */
3526 u64 max_extent_size
;
3528 /* Total free space from free space cache, not always contiguous */
3529 u64 total_free_space
;
3534 /* Hint where to start looking for an empty space */
3537 /* Allocation policy */
3538 enum btrfs_extent_allocation_policy policy
;
3543 * Helper function for find_free_extent().
3545 * Return -ENOENT to inform caller that we need fallback to unclustered mode.
3546 * Return -EAGAIN to inform caller that we need to re-search this block group
3547 * Return >0 to inform caller that we find nothing
3548 * Return 0 means we have found a location and set ffe_ctl->found_offset.
3550 static int find_free_extent_clustered(struct btrfs_block_group
*bg
,
3551 struct find_free_extent_ctl
*ffe_ctl
,
3552 struct btrfs_block_group
**cluster_bg_ret
)
3554 struct btrfs_block_group
*cluster_bg
;
3555 struct btrfs_free_cluster
*last_ptr
= ffe_ctl
->last_ptr
;
3556 u64 aligned_cluster
;
3560 cluster_bg
= btrfs_lock_cluster(bg
, last_ptr
, ffe_ctl
->delalloc
);
3562 goto refill_cluster
;
3563 if (cluster_bg
!= bg
&& (cluster_bg
->ro
||
3564 !block_group_bits(cluster_bg
, ffe_ctl
->flags
)))
3565 goto release_cluster
;
3567 offset
= btrfs_alloc_from_cluster(cluster_bg
, last_ptr
,
3568 ffe_ctl
->num_bytes
, cluster_bg
->start
,
3569 &ffe_ctl
->max_extent_size
);
3571 /* We have a block, we're done */
3572 spin_unlock(&last_ptr
->refill_lock
);
3573 trace_btrfs_reserve_extent_cluster(cluster_bg
,
3574 ffe_ctl
->search_start
, ffe_ctl
->num_bytes
);
3575 *cluster_bg_ret
= cluster_bg
;
3576 ffe_ctl
->found_offset
= offset
;
3579 WARN_ON(last_ptr
->block_group
!= cluster_bg
);
3583 * If we are on LOOP_NO_EMPTY_SIZE, we can't set up a new clusters, so
3584 * lets just skip it and let the allocator find whatever block it can
3585 * find. If we reach this point, we will have tried the cluster
3586 * allocator plenty of times and not have found anything, so we are
3587 * likely way too fragmented for the clustering stuff to find anything.
3589 * However, if the cluster is taken from the current block group,
3590 * release the cluster first, so that we stand a better chance of
3591 * succeeding in the unclustered allocation.
3593 if (ffe_ctl
->loop
>= LOOP_NO_EMPTY_SIZE
&& cluster_bg
!= bg
) {
3594 spin_unlock(&last_ptr
->refill_lock
);
3595 btrfs_release_block_group(cluster_bg
, ffe_ctl
->delalloc
);
3599 /* This cluster didn't work out, free it and start over */
3600 btrfs_return_cluster_to_free_space(NULL
, last_ptr
);
3602 if (cluster_bg
!= bg
)
3603 btrfs_release_block_group(cluster_bg
, ffe_ctl
->delalloc
);
3606 if (ffe_ctl
->loop
>= LOOP_NO_EMPTY_SIZE
) {
3607 spin_unlock(&last_ptr
->refill_lock
);
3611 aligned_cluster
= max_t(u64
,
3612 ffe_ctl
->empty_cluster
+ ffe_ctl
->empty_size
,
3613 bg
->full_stripe_len
);
3614 ret
= btrfs_find_space_cluster(bg
, last_ptr
, ffe_ctl
->search_start
,
3615 ffe_ctl
->num_bytes
, aligned_cluster
);
3617 /* Now pull our allocation out of this cluster */
3618 offset
= btrfs_alloc_from_cluster(bg
, last_ptr
,
3619 ffe_ctl
->num_bytes
, ffe_ctl
->search_start
,
3620 &ffe_ctl
->max_extent_size
);
3622 /* We found one, proceed */
3623 spin_unlock(&last_ptr
->refill_lock
);
3624 trace_btrfs_reserve_extent_cluster(bg
,
3625 ffe_ctl
->search_start
,
3626 ffe_ctl
->num_bytes
);
3627 ffe_ctl
->found_offset
= offset
;
3630 } else if (!ffe_ctl
->cached
&& ffe_ctl
->loop
> LOOP_CACHING_NOWAIT
&&
3631 !ffe_ctl
->retry_clustered
) {
3632 spin_unlock(&last_ptr
->refill_lock
);
3634 ffe_ctl
->retry_clustered
= true;
3635 btrfs_wait_block_group_cache_progress(bg
, ffe_ctl
->num_bytes
+
3636 ffe_ctl
->empty_cluster
+ ffe_ctl
->empty_size
);
3640 * At this point we either didn't find a cluster or we weren't able to
3641 * allocate a block from our cluster. Free the cluster we've been
3642 * trying to use, and go to the next block group.
3644 btrfs_return_cluster_to_free_space(NULL
, last_ptr
);
3645 spin_unlock(&last_ptr
->refill_lock
);
3650 * Return >0 to inform caller that we find nothing
3651 * Return 0 when we found an free extent and set ffe_ctrl->found_offset
3652 * Return -EAGAIN to inform caller that we need to re-search this block group
3654 static int find_free_extent_unclustered(struct btrfs_block_group
*bg
,
3655 struct find_free_extent_ctl
*ffe_ctl
)
3657 struct btrfs_free_cluster
*last_ptr
= ffe_ctl
->last_ptr
;
3661 * We are doing an unclustered allocation, set the fragmented flag so
3662 * we don't bother trying to setup a cluster again until we get more
3665 if (unlikely(last_ptr
)) {
3666 spin_lock(&last_ptr
->lock
);
3667 last_ptr
->fragmented
= 1;
3668 spin_unlock(&last_ptr
->lock
);
3670 if (ffe_ctl
->cached
) {
3671 struct btrfs_free_space_ctl
*free_space_ctl
;
3673 free_space_ctl
= bg
->free_space_ctl
;
3674 spin_lock(&free_space_ctl
->tree_lock
);
3675 if (free_space_ctl
->free_space
<
3676 ffe_ctl
->num_bytes
+ ffe_ctl
->empty_cluster
+
3677 ffe_ctl
->empty_size
) {
3678 ffe_ctl
->total_free_space
= max_t(u64
,
3679 ffe_ctl
->total_free_space
,
3680 free_space_ctl
->free_space
);
3681 spin_unlock(&free_space_ctl
->tree_lock
);
3684 spin_unlock(&free_space_ctl
->tree_lock
);
3687 offset
= btrfs_find_space_for_alloc(bg
, ffe_ctl
->search_start
,
3688 ffe_ctl
->num_bytes
, ffe_ctl
->empty_size
,
3689 &ffe_ctl
->max_extent_size
);
3692 * If we didn't find a chunk, and we haven't failed on this block group
3693 * before, and this block group is in the middle of caching and we are
3694 * ok with waiting, then go ahead and wait for progress to be made, and
3695 * set @retry_unclustered to true.
3697 * If @retry_unclustered is true then we've already waited on this
3698 * block group once and should move on to the next block group.
3700 if (!offset
&& !ffe_ctl
->retry_unclustered
&& !ffe_ctl
->cached
&&
3701 ffe_ctl
->loop
> LOOP_CACHING_NOWAIT
) {
3702 btrfs_wait_block_group_cache_progress(bg
, ffe_ctl
->num_bytes
+
3703 ffe_ctl
->empty_size
);
3704 ffe_ctl
->retry_unclustered
= true;
3706 } else if (!offset
) {
3709 ffe_ctl
->found_offset
= offset
;
3713 static int do_allocation_clustered(struct btrfs_block_group
*block_group
,
3714 struct find_free_extent_ctl
*ffe_ctl
,
3715 struct btrfs_block_group
**bg_ret
)
3719 /* We want to try and use the cluster allocator, so lets look there */
3720 if (ffe_ctl
->last_ptr
&& ffe_ctl
->use_cluster
) {
3721 ret
= find_free_extent_clustered(block_group
, ffe_ctl
, bg_ret
);
3722 if (ret
>= 0 || ret
== -EAGAIN
)
3724 /* ret == -ENOENT case falls through */
3727 return find_free_extent_unclustered(block_group
, ffe_ctl
);
3731 * Tree-log block group locking
3732 * ============================
3734 * fs_info::treelog_bg_lock protects the fs_info::treelog_bg which
3735 * indicates the starting address of a block group, which is reserved only
3736 * for tree-log metadata.
3743 * fs_info::treelog_bg_lock
3747 * Simple allocator for sequential-only block group. It only allows sequential
3748 * allocation. No need to play with trees. This function also reserves the
3749 * bytes as in btrfs_add_reserved_bytes.
3751 static int do_allocation_zoned(struct btrfs_block_group
*block_group
,
3752 struct find_free_extent_ctl
*ffe_ctl
,
3753 struct btrfs_block_group
**bg_ret
)
3755 struct btrfs_fs_info
*fs_info
= block_group
->fs_info
;
3756 struct btrfs_space_info
*space_info
= block_group
->space_info
;
3757 struct btrfs_free_space_ctl
*ctl
= block_group
->free_space_ctl
;
3758 u64 start
= block_group
->start
;
3759 u64 num_bytes
= ffe_ctl
->num_bytes
;
3761 u64 bytenr
= block_group
->start
;
3763 u64 data_reloc_bytenr
;
3767 ASSERT(btrfs_is_zoned(block_group
->fs_info
));
3770 * Do not allow non-tree-log blocks in the dedicated tree-log block
3771 * group, and vice versa.
3773 spin_lock(&fs_info
->treelog_bg_lock
);
3774 log_bytenr
= fs_info
->treelog_bg
;
3775 skip
= log_bytenr
&& ((ffe_ctl
->for_treelog
&& bytenr
!= log_bytenr
) ||
3776 (!ffe_ctl
->for_treelog
&& bytenr
== log_bytenr
));
3777 spin_unlock(&fs_info
->treelog_bg_lock
);
3782 * Do not allow non-relocation blocks in the dedicated relocation block
3783 * group, and vice versa.
3785 spin_lock(&fs_info
->relocation_bg_lock
);
3786 data_reloc_bytenr
= fs_info
->data_reloc_bg
;
3787 if (data_reloc_bytenr
&&
3788 ((ffe_ctl
->for_data_reloc
&& bytenr
!= data_reloc_bytenr
) ||
3789 (!ffe_ctl
->for_data_reloc
&& bytenr
== data_reloc_bytenr
)))
3791 spin_unlock(&fs_info
->relocation_bg_lock
);
3795 spin_lock(&space_info
->lock
);
3796 spin_lock(&block_group
->lock
);
3797 spin_lock(&fs_info
->treelog_bg_lock
);
3798 spin_lock(&fs_info
->relocation_bg_lock
);
3800 ASSERT(!ffe_ctl
->for_treelog
||
3801 block_group
->start
== fs_info
->treelog_bg
||
3802 fs_info
->treelog_bg
== 0);
3803 ASSERT(!ffe_ctl
->for_data_reloc
||
3804 block_group
->start
== fs_info
->data_reloc_bg
||
3805 fs_info
->data_reloc_bg
== 0);
3807 if (block_group
->ro
|| block_group
->zoned_data_reloc_ongoing
) {
3813 * Do not allow currently using block group to be tree-log dedicated
3816 if (ffe_ctl
->for_treelog
&& !fs_info
->treelog_bg
&&
3817 (block_group
->used
|| block_group
->reserved
)) {
3823 * Do not allow currently used block group to be the data relocation
3824 * dedicated block group.
3826 if (ffe_ctl
->for_data_reloc
&& !fs_info
->data_reloc_bg
&&
3827 (block_group
->used
|| block_group
->reserved
)) {
3832 avail
= block_group
->length
- block_group
->alloc_offset
;
3833 if (avail
< num_bytes
) {
3834 if (ffe_ctl
->max_extent_size
< avail
) {
3836 * With sequential allocator, free space is always
3839 ffe_ctl
->max_extent_size
= avail
;
3840 ffe_ctl
->total_free_space
= avail
;
3846 if (ffe_ctl
->for_treelog
&& !fs_info
->treelog_bg
)
3847 fs_info
->treelog_bg
= block_group
->start
;
3849 if (ffe_ctl
->for_data_reloc
&& !fs_info
->data_reloc_bg
)
3850 fs_info
->data_reloc_bg
= block_group
->start
;
3852 ffe_ctl
->found_offset
= start
+ block_group
->alloc_offset
;
3853 block_group
->alloc_offset
+= num_bytes
;
3854 spin_lock(&ctl
->tree_lock
);
3855 ctl
->free_space
-= num_bytes
;
3856 spin_unlock(&ctl
->tree_lock
);
3859 * We do not check if found_offset is aligned to stripesize. The
3860 * address is anyway rewritten when using zone append writing.
3863 ffe_ctl
->search_start
= ffe_ctl
->found_offset
;
3866 if (ret
&& ffe_ctl
->for_treelog
)
3867 fs_info
->treelog_bg
= 0;
3868 if (ret
&& ffe_ctl
->for_data_reloc
&&
3869 fs_info
->data_reloc_bg
== block_group
->start
) {
3871 * Do not allow further allocations from this block group.
3872 * Compared to increasing the ->ro, setting the
3873 * ->zoned_data_reloc_ongoing flag still allows nocow
3874 * writers to come in. See btrfs_inc_nocow_writers().
3876 * We need to disable an allocation to avoid an allocation of
3877 * regular (non-relocation data) extent. With mix of relocation
3878 * extents and regular extents, we can dispatch WRITE commands
3879 * (for relocation extents) and ZONE APPEND commands (for
3880 * regular extents) at the same time to the same zone, which
3881 * easily break the write pointer.
3883 block_group
->zoned_data_reloc_ongoing
= 1;
3884 fs_info
->data_reloc_bg
= 0;
3886 spin_unlock(&fs_info
->relocation_bg_lock
);
3887 spin_unlock(&fs_info
->treelog_bg_lock
);
3888 spin_unlock(&block_group
->lock
);
3889 spin_unlock(&space_info
->lock
);
3893 static int do_allocation(struct btrfs_block_group
*block_group
,
3894 struct find_free_extent_ctl
*ffe_ctl
,
3895 struct btrfs_block_group
**bg_ret
)
3897 switch (ffe_ctl
->policy
) {
3898 case BTRFS_EXTENT_ALLOC_CLUSTERED
:
3899 return do_allocation_clustered(block_group
, ffe_ctl
, bg_ret
);
3900 case BTRFS_EXTENT_ALLOC_ZONED
:
3901 return do_allocation_zoned(block_group
, ffe_ctl
, bg_ret
);
3907 static void release_block_group(struct btrfs_block_group
*block_group
,
3908 struct find_free_extent_ctl
*ffe_ctl
,
3911 switch (ffe_ctl
->policy
) {
3912 case BTRFS_EXTENT_ALLOC_CLUSTERED
:
3913 ffe_ctl
->retry_clustered
= false;
3914 ffe_ctl
->retry_unclustered
= false;
3916 case BTRFS_EXTENT_ALLOC_ZONED
:
3923 BUG_ON(btrfs_bg_flags_to_raid_index(block_group
->flags
) !=
3925 btrfs_release_block_group(block_group
, delalloc
);
3928 static void found_extent_clustered(struct find_free_extent_ctl
*ffe_ctl
,
3929 struct btrfs_key
*ins
)
3931 struct btrfs_free_cluster
*last_ptr
= ffe_ctl
->last_ptr
;
3933 if (!ffe_ctl
->use_cluster
&& last_ptr
) {
3934 spin_lock(&last_ptr
->lock
);
3935 last_ptr
->window_start
= ins
->objectid
;
3936 spin_unlock(&last_ptr
->lock
);
3940 static void found_extent(struct find_free_extent_ctl
*ffe_ctl
,
3941 struct btrfs_key
*ins
)
3943 switch (ffe_ctl
->policy
) {
3944 case BTRFS_EXTENT_ALLOC_CLUSTERED
:
3945 found_extent_clustered(ffe_ctl
, ins
);
3947 case BTRFS_EXTENT_ALLOC_ZONED
:
3955 static int chunk_allocation_failed(struct find_free_extent_ctl
*ffe_ctl
)
3957 switch (ffe_ctl
->policy
) {
3958 case BTRFS_EXTENT_ALLOC_CLUSTERED
:
3960 * If we can't allocate a new chunk we've already looped through
3961 * at least once, move on to the NO_EMPTY_SIZE case.
3963 ffe_ctl
->loop
= LOOP_NO_EMPTY_SIZE
;
3965 case BTRFS_EXTENT_ALLOC_ZONED
:
3974 * Return >0 means caller needs to re-search for free extent
3975 * Return 0 means we have the needed free extent.
3976 * Return <0 means we failed to locate any free extent.
3978 static int find_free_extent_update_loop(struct btrfs_fs_info
*fs_info
,
3979 struct btrfs_key
*ins
,
3980 struct find_free_extent_ctl
*ffe_ctl
,
3983 struct btrfs_root
*root
= fs_info
->extent_root
;
3986 if ((ffe_ctl
->loop
== LOOP_CACHING_NOWAIT
) &&
3987 ffe_ctl
->have_caching_bg
&& !ffe_ctl
->orig_have_caching_bg
)
3988 ffe_ctl
->orig_have_caching_bg
= true;
3990 if (!ins
->objectid
&& ffe_ctl
->loop
>= LOOP_CACHING_WAIT
&&
3991 ffe_ctl
->have_caching_bg
)
3994 if (!ins
->objectid
&& ++(ffe_ctl
->index
) < BTRFS_NR_RAID_TYPES
)
3997 if (ins
->objectid
) {
3998 found_extent(ffe_ctl
, ins
);
4003 * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
4004 * caching kthreads as we move along
4005 * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
4006 * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
4007 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
4010 if (ffe_ctl
->loop
< LOOP_NO_EMPTY_SIZE
) {
4012 if (ffe_ctl
->loop
== LOOP_CACHING_NOWAIT
) {
4014 * We want to skip the LOOP_CACHING_WAIT step if we
4015 * don't have any uncached bgs and we've already done a
4016 * full search through.
4018 if (ffe_ctl
->orig_have_caching_bg
|| !full_search
)
4019 ffe_ctl
->loop
= LOOP_CACHING_WAIT
;
4021 ffe_ctl
->loop
= LOOP_ALLOC_CHUNK
;
4026 if (ffe_ctl
->loop
== LOOP_ALLOC_CHUNK
) {
4027 struct btrfs_trans_handle
*trans
;
4030 trans
= current
->journal_info
;
4034 trans
= btrfs_join_transaction(root
);
4036 if (IS_ERR(trans
)) {
4037 ret
= PTR_ERR(trans
);
4041 ret
= btrfs_chunk_alloc(trans
, ffe_ctl
->flags
,
4044 /* Do not bail out on ENOSPC since we can do more. */
4046 ret
= chunk_allocation_failed(ffe_ctl
);
4048 btrfs_abort_transaction(trans
, ret
);
4052 btrfs_end_transaction(trans
);
4057 if (ffe_ctl
->loop
== LOOP_NO_EMPTY_SIZE
) {
4058 if (ffe_ctl
->policy
!= BTRFS_EXTENT_ALLOC_CLUSTERED
)
4062 * Don't loop again if we already have no empty_size and
4065 if (ffe_ctl
->empty_size
== 0 &&
4066 ffe_ctl
->empty_cluster
== 0)
4068 ffe_ctl
->empty_size
= 0;
4069 ffe_ctl
->empty_cluster
= 0;
4076 static int prepare_allocation_clustered(struct btrfs_fs_info
*fs_info
,
4077 struct find_free_extent_ctl
*ffe_ctl
,
4078 struct btrfs_space_info
*space_info
,
4079 struct btrfs_key
*ins
)
4082 * If our free space is heavily fragmented we may not be able to make
4083 * big contiguous allocations, so instead of doing the expensive search
4084 * for free space, simply return ENOSPC with our max_extent_size so we
4085 * can go ahead and search for a more manageable chunk.
4087 * If our max_extent_size is large enough for our allocation simply
4088 * disable clustering since we will likely not be able to find enough
4089 * space to create a cluster and induce latency trying.
4091 if (space_info
->max_extent_size
) {
4092 spin_lock(&space_info
->lock
);
4093 if (space_info
->max_extent_size
&&
4094 ffe_ctl
->num_bytes
> space_info
->max_extent_size
) {
4095 ins
->offset
= space_info
->max_extent_size
;
4096 spin_unlock(&space_info
->lock
);
4098 } else if (space_info
->max_extent_size
) {
4099 ffe_ctl
->use_cluster
= false;
4101 spin_unlock(&space_info
->lock
);
4104 ffe_ctl
->last_ptr
= fetch_cluster_info(fs_info
, space_info
,
4105 &ffe_ctl
->empty_cluster
);
4106 if (ffe_ctl
->last_ptr
) {
4107 struct btrfs_free_cluster
*last_ptr
= ffe_ctl
->last_ptr
;
4109 spin_lock(&last_ptr
->lock
);
4110 if (last_ptr
->block_group
)
4111 ffe_ctl
->hint_byte
= last_ptr
->window_start
;
4112 if (last_ptr
->fragmented
) {
4114 * We still set window_start so we can keep track of the
4115 * last place we found an allocation to try and save
4118 ffe_ctl
->hint_byte
= last_ptr
->window_start
;
4119 ffe_ctl
->use_cluster
= false;
4121 spin_unlock(&last_ptr
->lock
);
4127 static int prepare_allocation(struct btrfs_fs_info
*fs_info
,
4128 struct find_free_extent_ctl
*ffe_ctl
,
4129 struct btrfs_space_info
*space_info
,
4130 struct btrfs_key
*ins
)
4132 switch (ffe_ctl
->policy
) {
4133 case BTRFS_EXTENT_ALLOC_CLUSTERED
:
4134 return prepare_allocation_clustered(fs_info
, ffe_ctl
,
4136 case BTRFS_EXTENT_ALLOC_ZONED
:
4137 if (ffe_ctl
->for_treelog
) {
4138 spin_lock(&fs_info
->treelog_bg_lock
);
4139 if (fs_info
->treelog_bg
)
4140 ffe_ctl
->hint_byte
= fs_info
->treelog_bg
;
4141 spin_unlock(&fs_info
->treelog_bg_lock
);
4143 if (ffe_ctl
->for_data_reloc
) {
4144 spin_lock(&fs_info
->relocation_bg_lock
);
4145 if (fs_info
->data_reloc_bg
)
4146 ffe_ctl
->hint_byte
= fs_info
->data_reloc_bg
;
4147 spin_unlock(&fs_info
->relocation_bg_lock
);
4156 * walks the btree of allocated extents and find a hole of a given size.
4157 * The key ins is changed to record the hole:
4158 * ins->objectid == start position
4159 * ins->flags = BTRFS_EXTENT_ITEM_KEY
4160 * ins->offset == the size of the hole.
4161 * Any available blocks before search_start are skipped.
4163 * If there is no suitable free space, we will record the max size of
4164 * the free space extent currently.
4166 * The overall logic and call chain:
4168 * find_free_extent()
4169 * |- Iterate through all block groups
4170 * | |- Get a valid block group
4171 * | |- Try to do clustered allocation in that block group
4172 * | |- Try to do unclustered allocation in that block group
4173 * | |- Check if the result is valid
4174 * | | |- If valid, then exit
4175 * | |- Jump to next block group
4177 * |- Push harder to find free extents
4178 * |- If not found, re-iterate all block groups
4180 static noinline
int find_free_extent(struct btrfs_root
*root
,
4181 u64 ram_bytes
, u64 num_bytes
, u64 empty_size
,
4182 u64 hint_byte_orig
, struct btrfs_key
*ins
,
4183 u64 flags
, int delalloc
)
4185 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4187 int cache_block_group_error
= 0;
4188 struct btrfs_block_group
*block_group
= NULL
;
4189 struct find_free_extent_ctl ffe_ctl
= {0};
4190 struct btrfs_space_info
*space_info
;
4191 bool full_search
= false;
4192 bool for_treelog
= (root
->root_key
.objectid
== BTRFS_TREE_LOG_OBJECTID
);
4193 bool for_data_reloc
= (btrfs_is_data_reloc_root(root
) &&
4194 flags
& BTRFS_BLOCK_GROUP_DATA
);
4196 WARN_ON(num_bytes
< fs_info
->sectorsize
);
4198 ffe_ctl
.num_bytes
= num_bytes
;
4199 ffe_ctl
.empty_size
= empty_size
;
4200 ffe_ctl
.flags
= flags
;
4201 ffe_ctl
.search_start
= 0;
4202 ffe_ctl
.delalloc
= delalloc
;
4203 ffe_ctl
.index
= btrfs_bg_flags_to_raid_index(flags
);
4204 ffe_ctl
.have_caching_bg
= false;
4205 ffe_ctl
.orig_have_caching_bg
= false;
4206 ffe_ctl
.found_offset
= 0;
4207 ffe_ctl
.hint_byte
= hint_byte_orig
;
4208 ffe_ctl
.for_treelog
= for_treelog
;
4209 ffe_ctl
.for_data_reloc
= for_data_reloc
;
4210 ffe_ctl
.policy
= BTRFS_EXTENT_ALLOC_CLUSTERED
;
4212 /* For clustered allocation */
4213 ffe_ctl
.retry_clustered
= false;
4214 ffe_ctl
.retry_unclustered
= false;
4215 ffe_ctl
.last_ptr
= NULL
;
4216 ffe_ctl
.use_cluster
= true;
4218 if (btrfs_is_zoned(fs_info
))
4219 ffe_ctl
.policy
= BTRFS_EXTENT_ALLOC_ZONED
;
4221 ins
->type
= BTRFS_EXTENT_ITEM_KEY
;
4225 trace_find_free_extent(root
, num_bytes
, empty_size
, flags
);
4227 space_info
= btrfs_find_space_info(fs_info
, flags
);
4229 btrfs_err(fs_info
, "No space info for %llu", flags
);
4233 ret
= prepare_allocation(fs_info
, &ffe_ctl
, space_info
, ins
);
4237 ffe_ctl
.search_start
= max(ffe_ctl
.search_start
,
4238 first_logical_byte(fs_info
, 0));
4239 ffe_ctl
.search_start
= max(ffe_ctl
.search_start
, ffe_ctl
.hint_byte
);
4240 if (ffe_ctl
.search_start
== ffe_ctl
.hint_byte
) {
4241 block_group
= btrfs_lookup_block_group(fs_info
,
4242 ffe_ctl
.search_start
);
4244 * we don't want to use the block group if it doesn't match our
4245 * allocation bits, or if its not cached.
4247 * However if we are re-searching with an ideal block group
4248 * picked out then we don't care that the block group is cached.
4250 if (block_group
&& block_group_bits(block_group
, flags
) &&
4251 block_group
->cached
!= BTRFS_CACHE_NO
) {
4252 down_read(&space_info
->groups_sem
);
4253 if (list_empty(&block_group
->list
) ||
4256 * someone is removing this block group,
4257 * we can't jump into the have_block_group
4258 * target because our list pointers are not
4261 btrfs_put_block_group(block_group
);
4262 up_read(&space_info
->groups_sem
);
4264 ffe_ctl
.index
= btrfs_bg_flags_to_raid_index(
4265 block_group
->flags
);
4266 btrfs_lock_block_group(block_group
, delalloc
);
4267 goto have_block_group
;
4269 } else if (block_group
) {
4270 btrfs_put_block_group(block_group
);
4274 ffe_ctl
.have_caching_bg
= false;
4275 if (ffe_ctl
.index
== btrfs_bg_flags_to_raid_index(flags
) ||
4278 down_read(&space_info
->groups_sem
);
4279 list_for_each_entry(block_group
,
4280 &space_info
->block_groups
[ffe_ctl
.index
], list
) {
4281 struct btrfs_block_group
*bg_ret
;
4283 /* If the block group is read-only, we can skip it entirely. */
4284 if (unlikely(block_group
->ro
)) {
4286 btrfs_clear_treelog_bg(block_group
);
4287 if (ffe_ctl
.for_data_reloc
)
4288 btrfs_clear_data_reloc_bg(block_group
);
4292 btrfs_grab_block_group(block_group
, delalloc
);
4293 ffe_ctl
.search_start
= block_group
->start
;
4296 * this can happen if we end up cycling through all the
4297 * raid types, but we want to make sure we only allocate
4298 * for the proper type.
4300 if (!block_group_bits(block_group
, flags
)) {
4301 u64 extra
= BTRFS_BLOCK_GROUP_DUP
|
4302 BTRFS_BLOCK_GROUP_RAID1_MASK
|
4303 BTRFS_BLOCK_GROUP_RAID56_MASK
|
4304 BTRFS_BLOCK_GROUP_RAID10
;
4307 * if they asked for extra copies and this block group
4308 * doesn't provide them, bail. This does allow us to
4309 * fill raid0 from raid1.
4311 if ((flags
& extra
) && !(block_group
->flags
& extra
))
4315 * This block group has different flags than we want.
4316 * It's possible that we have MIXED_GROUP flag but no
4317 * block group is mixed. Just skip such block group.
4319 btrfs_release_block_group(block_group
, delalloc
);
4324 ffe_ctl
.cached
= btrfs_block_group_done(block_group
);
4325 if (unlikely(!ffe_ctl
.cached
)) {
4326 ffe_ctl
.have_caching_bg
= true;
4327 ret
= btrfs_cache_block_group(block_group
, 0);
4330 * If we get ENOMEM here or something else we want to
4331 * try other block groups, because it may not be fatal.
4332 * However if we can't find anything else we need to
4333 * save our return here so that we return the actual
4334 * error that caused problems, not ENOSPC.
4337 if (!cache_block_group_error
)
4338 cache_block_group_error
= ret
;
4345 if (unlikely(block_group
->cached
== BTRFS_CACHE_ERROR
))
4349 ret
= do_allocation(block_group
, &ffe_ctl
, &bg_ret
);
4351 if (bg_ret
&& bg_ret
!= block_group
) {
4352 btrfs_release_block_group(block_group
, delalloc
);
4353 block_group
= bg_ret
;
4355 } else if (ret
== -EAGAIN
) {
4356 goto have_block_group
;
4357 } else if (ret
> 0) {
4362 ffe_ctl
.search_start
= round_up(ffe_ctl
.found_offset
,
4363 fs_info
->stripesize
);
4365 /* move on to the next group */
4366 if (ffe_ctl
.search_start
+ num_bytes
>
4367 block_group
->start
+ block_group
->length
) {
4368 btrfs_add_free_space_unused(block_group
,
4369 ffe_ctl
.found_offset
, num_bytes
);
4373 if (ffe_ctl
.found_offset
< ffe_ctl
.search_start
)
4374 btrfs_add_free_space_unused(block_group
,
4375 ffe_ctl
.found_offset
,
4376 ffe_ctl
.search_start
- ffe_ctl
.found_offset
);
4378 ret
= btrfs_add_reserved_bytes(block_group
, ram_bytes
,
4379 num_bytes
, delalloc
);
4380 if (ret
== -EAGAIN
) {
4381 btrfs_add_free_space_unused(block_group
,
4382 ffe_ctl
.found_offset
, num_bytes
);
4385 btrfs_inc_block_group_reservations(block_group
);
4387 /* we are all good, lets return */
4388 ins
->objectid
= ffe_ctl
.search_start
;
4389 ins
->offset
= num_bytes
;
4391 trace_btrfs_reserve_extent(block_group
, ffe_ctl
.search_start
,
4393 btrfs_release_block_group(block_group
, delalloc
);
4396 release_block_group(block_group
, &ffe_ctl
, delalloc
);
4399 up_read(&space_info
->groups_sem
);
4401 ret
= find_free_extent_update_loop(fs_info
, ins
, &ffe_ctl
, full_search
);
4405 if (ret
== -ENOSPC
&& !cache_block_group_error
) {
4407 * Use ffe_ctl->total_free_space as fallback if we can't find
4408 * any contiguous hole.
4410 if (!ffe_ctl
.max_extent_size
)
4411 ffe_ctl
.max_extent_size
= ffe_ctl
.total_free_space
;
4412 spin_lock(&space_info
->lock
);
4413 space_info
->max_extent_size
= ffe_ctl
.max_extent_size
;
4414 spin_unlock(&space_info
->lock
);
4415 ins
->offset
= ffe_ctl
.max_extent_size
;
4416 } else if (ret
== -ENOSPC
) {
4417 ret
= cache_block_group_error
;
4423 * btrfs_reserve_extent - entry point to the extent allocator. Tries to find a
4424 * hole that is at least as big as @num_bytes.
4426 * @root - The root that will contain this extent
4428 * @ram_bytes - The amount of space in ram that @num_bytes take. This
4429 * is used for accounting purposes. This value differs
4430 * from @num_bytes only in the case of compressed extents.
4432 * @num_bytes - Number of bytes to allocate on-disk.
4434 * @min_alloc_size - Indicates the minimum amount of space that the
4435 * allocator should try to satisfy. In some cases
4436 * @num_bytes may be larger than what is required and if
4437 * the filesystem is fragmented then allocation fails.
4438 * However, the presence of @min_alloc_size gives a
4439 * chance to try and satisfy the smaller allocation.
4441 * @empty_size - A hint that you plan on doing more COW. This is the
4442 * size in bytes the allocator should try to find free
4443 * next to the block it returns. This is just a hint and
4444 * may be ignored by the allocator.
4446 * @hint_byte - Hint to the allocator to start searching above the byte
4447 * address passed. It might be ignored.
4449 * @ins - This key is modified to record the found hole. It will
4450 * have the following values:
4451 * ins->objectid == start position
4452 * ins->flags = BTRFS_EXTENT_ITEM_KEY
4453 * ins->offset == the size of the hole.
4455 * @is_data - Boolean flag indicating whether an extent is
4456 * allocated for data (true) or metadata (false)
4458 * @delalloc - Boolean flag indicating whether this allocation is for
4459 * delalloc or not. If 'true' data_rwsem of block groups
4460 * is going to be acquired.
4463 * Returns 0 when an allocation succeeded or < 0 when an error occurred. In
4464 * case -ENOSPC is returned then @ins->offset will contain the size of the
4465 * largest available hole the allocator managed to find.
4467 int btrfs_reserve_extent(struct btrfs_root
*root
, u64 ram_bytes
,
4468 u64 num_bytes
, u64 min_alloc_size
,
4469 u64 empty_size
, u64 hint_byte
,
4470 struct btrfs_key
*ins
, int is_data
, int delalloc
)
4472 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4473 bool final_tried
= num_bytes
== min_alloc_size
;
4476 bool for_treelog
= (root
->root_key
.objectid
== BTRFS_TREE_LOG_OBJECTID
);
4477 bool for_data_reloc
= (btrfs_is_data_reloc_root(root
) && is_data
);
4479 flags
= get_alloc_profile_by_root(root
, is_data
);
4481 WARN_ON(num_bytes
< fs_info
->sectorsize
);
4482 ret
= find_free_extent(root
, ram_bytes
, num_bytes
, empty_size
,
4483 hint_byte
, ins
, flags
, delalloc
);
4484 if (!ret
&& !is_data
) {
4485 btrfs_dec_block_group_reservations(fs_info
, ins
->objectid
);
4486 } else if (ret
== -ENOSPC
) {
4487 if (!final_tried
&& ins
->offset
) {
4488 num_bytes
= min(num_bytes
>> 1, ins
->offset
);
4489 num_bytes
= round_down(num_bytes
,
4490 fs_info
->sectorsize
);
4491 num_bytes
= max(num_bytes
, min_alloc_size
);
4492 ram_bytes
= num_bytes
;
4493 if (num_bytes
== min_alloc_size
)
4496 } else if (btrfs_test_opt(fs_info
, ENOSPC_DEBUG
)) {
4497 struct btrfs_space_info
*sinfo
;
4499 sinfo
= btrfs_find_space_info(fs_info
, flags
);
4501 "allocation failed flags %llu, wanted %llu tree-log %d, relocation: %d",
4502 flags
, num_bytes
, for_treelog
, for_data_reloc
);
4504 btrfs_dump_space_info(fs_info
, sinfo
,
4512 int btrfs_free_reserved_extent(struct btrfs_fs_info
*fs_info
,
4513 u64 start
, u64 len
, int delalloc
)
4515 struct btrfs_block_group
*cache
;
4517 cache
= btrfs_lookup_block_group(fs_info
, start
);
4519 btrfs_err(fs_info
, "Unable to find block group for %llu",
4524 btrfs_add_free_space(cache
, start
, len
);
4525 btrfs_free_reserved_bytes(cache
, len
, delalloc
);
4526 trace_btrfs_reserved_extent_free(fs_info
, start
, len
);
4528 btrfs_put_block_group(cache
);
4532 int btrfs_pin_reserved_extent(struct btrfs_trans_handle
*trans
, u64 start
,
4535 struct btrfs_block_group
*cache
;
4538 cache
= btrfs_lookup_block_group(trans
->fs_info
, start
);
4540 btrfs_err(trans
->fs_info
, "unable to find block group for %llu",
4545 ret
= pin_down_extent(trans
, cache
, start
, len
, 1);
4546 btrfs_put_block_group(cache
);
4550 static int alloc_reserved_file_extent(struct btrfs_trans_handle
*trans
,
4551 u64 parent
, u64 root_objectid
,
4552 u64 flags
, u64 owner
, u64 offset
,
4553 struct btrfs_key
*ins
, int ref_mod
)
4555 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
4557 struct btrfs_extent_item
*extent_item
;
4558 struct btrfs_extent_inline_ref
*iref
;
4559 struct btrfs_path
*path
;
4560 struct extent_buffer
*leaf
;
4565 type
= BTRFS_SHARED_DATA_REF_KEY
;
4567 type
= BTRFS_EXTENT_DATA_REF_KEY
;
4569 size
= sizeof(*extent_item
) + btrfs_extent_inline_ref_size(type
);
4571 path
= btrfs_alloc_path();
4575 ret
= btrfs_insert_empty_item(trans
, fs_info
->extent_root
, path
,
4578 btrfs_free_path(path
);
4582 leaf
= path
->nodes
[0];
4583 extent_item
= btrfs_item_ptr(leaf
, path
->slots
[0],
4584 struct btrfs_extent_item
);
4585 btrfs_set_extent_refs(leaf
, extent_item
, ref_mod
);
4586 btrfs_set_extent_generation(leaf
, extent_item
, trans
->transid
);
4587 btrfs_set_extent_flags(leaf
, extent_item
,
4588 flags
| BTRFS_EXTENT_FLAG_DATA
);
4590 iref
= (struct btrfs_extent_inline_ref
*)(extent_item
+ 1);
4591 btrfs_set_extent_inline_ref_type(leaf
, iref
, type
);
4593 struct btrfs_shared_data_ref
*ref
;
4594 ref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
4595 btrfs_set_extent_inline_ref_offset(leaf
, iref
, parent
);
4596 btrfs_set_shared_data_ref_count(leaf
, ref
, ref_mod
);
4598 struct btrfs_extent_data_ref
*ref
;
4599 ref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
4600 btrfs_set_extent_data_ref_root(leaf
, ref
, root_objectid
);
4601 btrfs_set_extent_data_ref_objectid(leaf
, ref
, owner
);
4602 btrfs_set_extent_data_ref_offset(leaf
, ref
, offset
);
4603 btrfs_set_extent_data_ref_count(leaf
, ref
, ref_mod
);
4606 btrfs_mark_buffer_dirty(path
->nodes
[0]);
4607 btrfs_free_path(path
);
4609 ret
= remove_from_free_space_tree(trans
, ins
->objectid
, ins
->offset
);
4613 ret
= btrfs_update_block_group(trans
, ins
->objectid
, ins
->offset
, 1);
4614 if (ret
) { /* -ENOENT, logic error */
4615 btrfs_err(fs_info
, "update block group failed for %llu %llu",
4616 ins
->objectid
, ins
->offset
);
4619 trace_btrfs_reserved_extent_alloc(fs_info
, ins
->objectid
, ins
->offset
);
4623 static int alloc_reserved_tree_block(struct btrfs_trans_handle
*trans
,
4624 struct btrfs_delayed_ref_node
*node
,
4625 struct btrfs_delayed_extent_op
*extent_op
)
4627 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
4629 struct btrfs_extent_item
*extent_item
;
4630 struct btrfs_key extent_key
;
4631 struct btrfs_tree_block_info
*block_info
;
4632 struct btrfs_extent_inline_ref
*iref
;
4633 struct btrfs_path
*path
;
4634 struct extent_buffer
*leaf
;
4635 struct btrfs_delayed_tree_ref
*ref
;
4636 u32 size
= sizeof(*extent_item
) + sizeof(*iref
);
4638 u64 flags
= extent_op
->flags_to_set
;
4639 bool skinny_metadata
= btrfs_fs_incompat(fs_info
, SKINNY_METADATA
);
4641 ref
= btrfs_delayed_node_to_tree_ref(node
);
4643 extent_key
.objectid
= node
->bytenr
;
4644 if (skinny_metadata
) {
4645 extent_key
.offset
= ref
->level
;
4646 extent_key
.type
= BTRFS_METADATA_ITEM_KEY
;
4647 num_bytes
= fs_info
->nodesize
;
4649 extent_key
.offset
= node
->num_bytes
;
4650 extent_key
.type
= BTRFS_EXTENT_ITEM_KEY
;
4651 size
+= sizeof(*block_info
);
4652 num_bytes
= node
->num_bytes
;
4655 path
= btrfs_alloc_path();
4659 ret
= btrfs_insert_empty_item(trans
, fs_info
->extent_root
, path
,
4662 btrfs_free_path(path
);
4666 leaf
= path
->nodes
[0];
4667 extent_item
= btrfs_item_ptr(leaf
, path
->slots
[0],
4668 struct btrfs_extent_item
);
4669 btrfs_set_extent_refs(leaf
, extent_item
, 1);
4670 btrfs_set_extent_generation(leaf
, extent_item
, trans
->transid
);
4671 btrfs_set_extent_flags(leaf
, extent_item
,
4672 flags
| BTRFS_EXTENT_FLAG_TREE_BLOCK
);
4674 if (skinny_metadata
) {
4675 iref
= (struct btrfs_extent_inline_ref
*)(extent_item
+ 1);
4677 block_info
= (struct btrfs_tree_block_info
*)(extent_item
+ 1);
4678 btrfs_set_tree_block_key(leaf
, block_info
, &extent_op
->key
);
4679 btrfs_set_tree_block_level(leaf
, block_info
, ref
->level
);
4680 iref
= (struct btrfs_extent_inline_ref
*)(block_info
+ 1);
4683 if (node
->type
== BTRFS_SHARED_BLOCK_REF_KEY
) {
4684 btrfs_set_extent_inline_ref_type(leaf
, iref
,
4685 BTRFS_SHARED_BLOCK_REF_KEY
);
4686 btrfs_set_extent_inline_ref_offset(leaf
, iref
, ref
->parent
);
4688 btrfs_set_extent_inline_ref_type(leaf
, iref
,
4689 BTRFS_TREE_BLOCK_REF_KEY
);
4690 btrfs_set_extent_inline_ref_offset(leaf
, iref
, ref
->root
);
4693 btrfs_mark_buffer_dirty(leaf
);
4694 btrfs_free_path(path
);
4696 ret
= remove_from_free_space_tree(trans
, extent_key
.objectid
,
4701 ret
= btrfs_update_block_group(trans
, extent_key
.objectid
,
4702 fs_info
->nodesize
, 1);
4703 if (ret
) { /* -ENOENT, logic error */
4704 btrfs_err(fs_info
, "update block group failed for %llu %llu",
4705 extent_key
.objectid
, extent_key
.offset
);
4709 trace_btrfs_reserved_extent_alloc(fs_info
, extent_key
.objectid
,
4714 int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle
*trans
,
4715 struct btrfs_root
*root
, u64 owner
,
4716 u64 offset
, u64 ram_bytes
,
4717 struct btrfs_key
*ins
)
4719 struct btrfs_ref generic_ref
= { 0 };
4721 BUG_ON(root
->root_key
.objectid
== BTRFS_TREE_LOG_OBJECTID
);
4723 btrfs_init_generic_ref(&generic_ref
, BTRFS_ADD_DELAYED_EXTENT
,
4724 ins
->objectid
, ins
->offset
, 0);
4725 btrfs_init_data_ref(&generic_ref
, root
->root_key
.objectid
, owner
,
4727 btrfs_ref_tree_mod(root
->fs_info
, &generic_ref
);
4729 return btrfs_add_delayed_data_ref(trans
, &generic_ref
, ram_bytes
);
4733 * this is used by the tree logging recovery code. It records that
4734 * an extent has been allocated and makes sure to clear the free
4735 * space cache bits as well
4737 int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle
*trans
,
4738 u64 root_objectid
, u64 owner
, u64 offset
,
4739 struct btrfs_key
*ins
)
4741 struct btrfs_fs_info
*fs_info
= trans
->fs_info
;
4743 struct btrfs_block_group
*block_group
;
4744 struct btrfs_space_info
*space_info
;
4747 * Mixed block groups will exclude before processing the log so we only
4748 * need to do the exclude dance if this fs isn't mixed.
4750 if (!btrfs_fs_incompat(fs_info
, MIXED_GROUPS
)) {
4751 ret
= __exclude_logged_extent(fs_info
, ins
->objectid
,
4757 block_group
= btrfs_lookup_block_group(fs_info
, ins
->objectid
);
4761 space_info
= block_group
->space_info
;
4762 spin_lock(&space_info
->lock
);
4763 spin_lock(&block_group
->lock
);
4764 space_info
->bytes_reserved
+= ins
->offset
;
4765 block_group
->reserved
+= ins
->offset
;
4766 spin_unlock(&block_group
->lock
);
4767 spin_unlock(&space_info
->lock
);
4769 ret
= alloc_reserved_file_extent(trans
, 0, root_objectid
, 0, owner
,
4772 btrfs_pin_extent(trans
, ins
->objectid
, ins
->offset
, 1);
4773 btrfs_put_block_group(block_group
);
4777 static struct extent_buffer
*
4778 btrfs_init_new_buffer(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
4779 u64 bytenr
, int level
, u64 owner
,
4780 enum btrfs_lock_nesting nest
)
4782 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4783 struct extent_buffer
*buf
;
4785 buf
= btrfs_find_create_tree_block(fs_info
, bytenr
, owner
, level
);
4790 * Extra safety check in case the extent tree is corrupted and extent
4791 * allocator chooses to use a tree block which is already used and
4794 if (buf
->lock_owner
== current
->pid
) {
4795 btrfs_err_rl(fs_info
,
4796 "tree block %llu owner %llu already locked by pid=%d, extent tree corruption detected",
4797 buf
->start
, btrfs_header_owner(buf
), current
->pid
);
4798 free_extent_buffer(buf
);
4799 return ERR_PTR(-EUCLEAN
);
4803 * This needs to stay, because we could allocate a freed block from an
4804 * old tree into a new tree, so we need to make sure this new block is
4805 * set to the appropriate level and owner.
4807 btrfs_set_buffer_lockdep_class(owner
, buf
, level
);
4808 __btrfs_tree_lock(buf
, nest
);
4809 btrfs_clean_tree_block(buf
);
4810 clear_bit(EXTENT_BUFFER_STALE
, &buf
->bflags
);
4811 clear_bit(EXTENT_BUFFER_NO_CHECK
, &buf
->bflags
);
4813 set_extent_buffer_uptodate(buf
);
4815 memzero_extent_buffer(buf
, 0, sizeof(struct btrfs_header
));
4816 btrfs_set_header_level(buf
, level
);
4817 btrfs_set_header_bytenr(buf
, buf
->start
);
4818 btrfs_set_header_generation(buf
, trans
->transid
);
4819 btrfs_set_header_backref_rev(buf
, BTRFS_MIXED_BACKREF_REV
);
4820 btrfs_set_header_owner(buf
, owner
);
4821 write_extent_buffer_fsid(buf
, fs_info
->fs_devices
->metadata_uuid
);
4822 write_extent_buffer_chunk_tree_uuid(buf
, fs_info
->chunk_tree_uuid
);
4823 if (root
->root_key
.objectid
== BTRFS_TREE_LOG_OBJECTID
) {
4824 buf
->log_index
= root
->log_transid
% 2;
4826 * we allow two log transactions at a time, use different
4827 * EXTENT bit to differentiate dirty pages.
4829 if (buf
->log_index
== 0)
4830 set_extent_dirty(&root
->dirty_log_pages
, buf
->start
,
4831 buf
->start
+ buf
->len
- 1, GFP_NOFS
);
4833 set_extent_new(&root
->dirty_log_pages
, buf
->start
,
4834 buf
->start
+ buf
->len
- 1);
4836 buf
->log_index
= -1;
4837 set_extent_dirty(&trans
->transaction
->dirty_pages
, buf
->start
,
4838 buf
->start
+ buf
->len
- 1, GFP_NOFS
);
4840 /* this returns a buffer locked for blocking */
4845 * finds a free extent and does all the dirty work required for allocation
4846 * returns the tree buffer or an ERR_PTR on error.
4848 struct extent_buffer
*btrfs_alloc_tree_block(struct btrfs_trans_handle
*trans
,
4849 struct btrfs_root
*root
,
4850 u64 parent
, u64 root_objectid
,
4851 const struct btrfs_disk_key
*key
,
4852 int level
, u64 hint
,
4854 enum btrfs_lock_nesting nest
)
4856 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4857 struct btrfs_key ins
;
4858 struct btrfs_block_rsv
*block_rsv
;
4859 struct extent_buffer
*buf
;
4860 struct btrfs_delayed_extent_op
*extent_op
;
4861 struct btrfs_ref generic_ref
= { 0 };
4864 u32 blocksize
= fs_info
->nodesize
;
4865 bool skinny_metadata
= btrfs_fs_incompat(fs_info
, SKINNY_METADATA
);
4867 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
4868 if (btrfs_is_testing(fs_info
)) {
4869 buf
= btrfs_init_new_buffer(trans
, root
, root
->alloc_bytenr
,
4870 level
, root_objectid
, nest
);
4872 root
->alloc_bytenr
+= blocksize
;
4877 block_rsv
= btrfs_use_block_rsv(trans
, root
, blocksize
);
4878 if (IS_ERR(block_rsv
))
4879 return ERR_CAST(block_rsv
);
4881 ret
= btrfs_reserve_extent(root
, blocksize
, blocksize
, blocksize
,
4882 empty_size
, hint
, &ins
, 0, 0);
4886 buf
= btrfs_init_new_buffer(trans
, root
, ins
.objectid
, level
,
4887 root_objectid
, nest
);
4890 goto out_free_reserved
;
4893 if (root_objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
4895 parent
= ins
.objectid
;
4896 flags
|= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
4900 if (root_objectid
!= BTRFS_TREE_LOG_OBJECTID
) {
4901 extent_op
= btrfs_alloc_delayed_extent_op();
4907 memcpy(&extent_op
->key
, key
, sizeof(extent_op
->key
));
4909 memset(&extent_op
->key
, 0, sizeof(extent_op
->key
));
4910 extent_op
->flags_to_set
= flags
;
4911 extent_op
->update_key
= skinny_metadata
? false : true;
4912 extent_op
->update_flags
= true;
4913 extent_op
->is_data
= false;
4914 extent_op
->level
= level
;
4916 btrfs_init_generic_ref(&generic_ref
, BTRFS_ADD_DELAYED_EXTENT
,
4917 ins
.objectid
, ins
.offset
, parent
);
4918 generic_ref
.real_root
= root
->root_key
.objectid
;
4919 btrfs_init_tree_ref(&generic_ref
, level
, root_objectid
,
4920 root
->root_key
.objectid
, false);
4921 btrfs_ref_tree_mod(fs_info
, &generic_ref
);
4922 ret
= btrfs_add_delayed_tree_ref(trans
, &generic_ref
, extent_op
);
4924 goto out_free_delayed
;
4929 btrfs_free_delayed_extent_op(extent_op
);
4931 btrfs_tree_unlock(buf
);
4932 free_extent_buffer(buf
);
4934 btrfs_free_reserved_extent(fs_info
, ins
.objectid
, ins
.offset
, 0);
4936 btrfs_unuse_block_rsv(fs_info
, block_rsv
, blocksize
);
4937 return ERR_PTR(ret
);
4940 struct walk_control
{
4941 u64 refs
[BTRFS_MAX_LEVEL
];
4942 u64 flags
[BTRFS_MAX_LEVEL
];
4943 struct btrfs_key update_progress
;
4944 struct btrfs_key drop_progress
;
4956 #define DROP_REFERENCE 1
4957 #define UPDATE_BACKREF 2
4959 static noinline
void reada_walk_down(struct btrfs_trans_handle
*trans
,
4960 struct btrfs_root
*root
,
4961 struct walk_control
*wc
,
4962 struct btrfs_path
*path
)
4964 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
4970 struct btrfs_key key
;
4971 struct extent_buffer
*eb
;
4976 if (path
->slots
[wc
->level
] < wc
->reada_slot
) {
4977 wc
->reada_count
= wc
->reada_count
* 2 / 3;
4978 wc
->reada_count
= max(wc
->reada_count
, 2);
4980 wc
->reada_count
= wc
->reada_count
* 3 / 2;
4981 wc
->reada_count
= min_t(int, wc
->reada_count
,
4982 BTRFS_NODEPTRS_PER_BLOCK(fs_info
));
4985 eb
= path
->nodes
[wc
->level
];
4986 nritems
= btrfs_header_nritems(eb
);
4988 for (slot
= path
->slots
[wc
->level
]; slot
< nritems
; slot
++) {
4989 if (nread
>= wc
->reada_count
)
4993 bytenr
= btrfs_node_blockptr(eb
, slot
);
4994 generation
= btrfs_node_ptr_generation(eb
, slot
);
4996 if (slot
== path
->slots
[wc
->level
])
4999 if (wc
->stage
== UPDATE_BACKREF
&&
5000 generation
<= root
->root_key
.offset
)
5003 /* We don't lock the tree block, it's OK to be racy here */
5004 ret
= btrfs_lookup_extent_info(trans
, fs_info
, bytenr
,
5005 wc
->level
- 1, 1, &refs
,
5007 /* We don't care about errors in readahead. */
5012 if (wc
->stage
== DROP_REFERENCE
) {
5016 if (wc
->level
== 1 &&
5017 (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
))
5019 if (!wc
->update_ref
||
5020 generation
<= root
->root_key
.offset
)
5022 btrfs_node_key_to_cpu(eb
, &key
, slot
);
5023 ret
= btrfs_comp_cpu_keys(&key
,
5024 &wc
->update_progress
);
5028 if (wc
->level
== 1 &&
5029 (flags
& BTRFS_BLOCK_FLAG_FULL_BACKREF
))
5033 btrfs_readahead_node_child(eb
, slot
);
5036 wc
->reada_slot
= slot
;
5040 * helper to process tree block while walking down the tree.
5042 * when wc->stage == UPDATE_BACKREF, this function updates
5043 * back refs for pointers in the block.
5045 * NOTE: return value 1 means we should stop walking down.
5047 static noinline
int walk_down_proc(struct btrfs_trans_handle
*trans
,
5048 struct btrfs_root
*root
,
5049 struct btrfs_path
*path
,
5050 struct walk_control
*wc
, int lookup_info
)
5052 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
5053 int level
= wc
->level
;
5054 struct extent_buffer
*eb
= path
->nodes
[level
];
5055 u64 flag
= BTRFS_BLOCK_FLAG_FULL_BACKREF
;
5058 if (wc
->stage
== UPDATE_BACKREF
&&
5059 btrfs_header_owner(eb
) != root
->root_key
.objectid
)
5063 * when reference count of tree block is 1, it won't increase
5064 * again. once full backref flag is set, we never clear it.
5067 ((wc
->stage
== DROP_REFERENCE
&& wc
->refs
[level
] != 1) ||
5068 (wc
->stage
== UPDATE_BACKREF
&& !(wc
->flags
[level
] & flag
)))) {
5069 BUG_ON(!path
->locks
[level
]);
5070 ret
= btrfs_lookup_extent_info(trans
, fs_info
,
5071 eb
->start
, level
, 1,
5074 BUG_ON(ret
== -ENOMEM
);
5077 BUG_ON(wc
->refs
[level
] == 0);
5080 if (wc
->stage
== DROP_REFERENCE
) {
5081 if (wc
->refs
[level
] > 1)
5084 if (path
->locks
[level
] && !wc
->keep_locks
) {
5085 btrfs_tree_unlock_rw(eb
, path
->locks
[level
]);
5086 path
->locks
[level
] = 0;
5091 /* wc->stage == UPDATE_BACKREF */
5092 if (!(wc
->flags
[level
] & flag
)) {
5093 BUG_ON(!path
->locks
[level
]);
5094 ret
= btrfs_inc_ref(trans
, root
, eb
, 1);
5095 BUG_ON(ret
); /* -ENOMEM */
5096 ret
= btrfs_dec_ref(trans
, root
, eb
, 0);
5097 BUG_ON(ret
); /* -ENOMEM */
5098 ret
= btrfs_set_disk_extent_flags(trans
, eb
, flag
,
5099 btrfs_header_level(eb
), 0);
5100 BUG_ON(ret
); /* -ENOMEM */
5101 wc
->flags
[level
] |= flag
;
5105 * the block is shared by multiple trees, so it's not good to
5106 * keep the tree lock
5108 if (path
->locks
[level
] && level
> 0) {
5109 btrfs_tree_unlock_rw(eb
, path
->locks
[level
]);
5110 path
->locks
[level
] = 0;
5116 * This is used to verify a ref exists for this root to deal with a bug where we
5117 * would have a drop_progress key that hadn't been updated properly.
5119 static int check_ref_exists(struct btrfs_trans_handle
*trans
,
5120 struct btrfs_root
*root
, u64 bytenr
, u64 parent
,
5123 struct btrfs_path
*path
;
5124 struct btrfs_extent_inline_ref
*iref
;
5127 path
= btrfs_alloc_path();
5131 ret
= lookup_extent_backref(trans
, path
, &iref
, bytenr
,
5132 root
->fs_info
->nodesize
, parent
,
5133 root
->root_key
.objectid
, level
, 0);
5134 btrfs_free_path(path
);
5143 * helper to process tree block pointer.
5145 * when wc->stage == DROP_REFERENCE, this function checks
5146 * reference count of the block pointed to. if the block
5147 * is shared and we need update back refs for the subtree
5148 * rooted at the block, this function changes wc->stage to
5149 * UPDATE_BACKREF. if the block is shared and there is no
5150 * need to update back, this function drops the reference
5153 * NOTE: return value 1 means we should stop walking down.
5155 static noinline
int do_walk_down(struct btrfs_trans_handle
*trans
,
5156 struct btrfs_root
*root
,
5157 struct btrfs_path
*path
,
5158 struct walk_control
*wc
, int *lookup_info
)
5160 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
5164 struct btrfs_key key
;
5165 struct btrfs_key first_key
;
5166 struct btrfs_ref ref
= { 0 };
5167 struct extent_buffer
*next
;
5168 int level
= wc
->level
;
5171 bool need_account
= false;
5173 generation
= btrfs_node_ptr_generation(path
->nodes
[level
],
5174 path
->slots
[level
]);
5176 * if the lower level block was created before the snapshot
5177 * was created, we know there is no need to update back refs
5180 if (wc
->stage
== UPDATE_BACKREF
&&
5181 generation
<= root
->root_key
.offset
) {
5186 bytenr
= btrfs_node_blockptr(path
->nodes
[level
], path
->slots
[level
]);
5187 btrfs_node_key_to_cpu(path
->nodes
[level
], &first_key
,
5188 path
->slots
[level
]);
5190 next
= find_extent_buffer(fs_info
, bytenr
);
5192 next
= btrfs_find_create_tree_block(fs_info
, bytenr
,
5193 root
->root_key
.objectid
, level
- 1);
5195 return PTR_ERR(next
);
5198 btrfs_tree_lock(next
);
5200 ret
= btrfs_lookup_extent_info(trans
, fs_info
, bytenr
, level
- 1, 1,
5201 &wc
->refs
[level
- 1],
5202 &wc
->flags
[level
- 1]);
5206 if (unlikely(wc
->refs
[level
- 1] == 0)) {
5207 btrfs_err(fs_info
, "Missing references.");
5213 if (wc
->stage
== DROP_REFERENCE
) {
5214 if (wc
->refs
[level
- 1] > 1) {
5215 need_account
= true;
5217 (wc
->flags
[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF
))
5220 if (!wc
->update_ref
||
5221 generation
<= root
->root_key
.offset
)
5224 btrfs_node_key_to_cpu(path
->nodes
[level
], &key
,
5225 path
->slots
[level
]);
5226 ret
= btrfs_comp_cpu_keys(&key
, &wc
->update_progress
);
5230 wc
->stage
= UPDATE_BACKREF
;
5231 wc
->shared_level
= level
- 1;
5235 (wc
->flags
[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF
))
5239 if (!btrfs_buffer_uptodate(next
, generation
, 0)) {
5240 btrfs_tree_unlock(next
);
5241 free_extent_buffer(next
);
5247 if (reada
&& level
== 1)
5248 reada_walk_down(trans
, root
, wc
, path
);
5249 next
= read_tree_block(fs_info
, bytenr
, root
->root_key
.objectid
,
5250 generation
, level
- 1, &first_key
);
5252 return PTR_ERR(next
);
5253 } else if (!extent_buffer_uptodate(next
)) {
5254 free_extent_buffer(next
);
5257 btrfs_tree_lock(next
);
5261 ASSERT(level
== btrfs_header_level(next
));
5262 if (level
!= btrfs_header_level(next
)) {
5263 btrfs_err(root
->fs_info
, "mismatched level");
5267 path
->nodes
[level
] = next
;
5268 path
->slots
[level
] = 0;
5269 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5275 wc
->refs
[level
- 1] = 0;
5276 wc
->flags
[level
- 1] = 0;
5277 if (wc
->stage
== DROP_REFERENCE
) {
5278 if (wc
->flags
[level
] & BTRFS_BLOCK_FLAG_FULL_BACKREF
) {
5279 parent
= path
->nodes
[level
]->start
;
5281 ASSERT(root
->root_key
.objectid
==
5282 btrfs_header_owner(path
->nodes
[level
]));
5283 if (root
->root_key
.objectid
!=
5284 btrfs_header_owner(path
->nodes
[level
])) {
5285 btrfs_err(root
->fs_info
,
5286 "mismatched block owner");
5294 * If we had a drop_progress we need to verify the refs are set
5295 * as expected. If we find our ref then we know that from here
5296 * on out everything should be correct, and we can clear the
5299 if (wc
->restarted
) {
5300 ret
= check_ref_exists(trans
, root
, bytenr
, parent
,
5311 * Reloc tree doesn't contribute to qgroup numbers, and we have
5312 * already accounted them at merge time (replace_path),
5313 * thus we could skip expensive subtree trace here.
5315 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
&&
5317 ret
= btrfs_qgroup_trace_subtree(trans
, next
,
5318 generation
, level
- 1);
5320 btrfs_err_rl(fs_info
,
5321 "Error %d accounting shared subtree. Quota is out of sync, rescan required.",
5327 * We need to update the next key in our walk control so we can
5328 * update the drop_progress key accordingly. We don't care if
5329 * find_next_key doesn't find a key because that means we're at
5330 * the end and are going to clean up now.
5332 wc
->drop_level
= level
;
5333 find_next_key(path
, level
, &wc
->drop_progress
);
5335 btrfs_init_generic_ref(&ref
, BTRFS_DROP_DELAYED_REF
, bytenr
,
5336 fs_info
->nodesize
, parent
);
5337 btrfs_init_tree_ref(&ref
, level
- 1, root
->root_key
.objectid
,
5339 ret
= btrfs_free_extent(trans
, &ref
);
5348 btrfs_tree_unlock(next
);
5349 free_extent_buffer(next
);
5355 * helper to process tree block while walking up the tree.
5357 * when wc->stage == DROP_REFERENCE, this function drops
5358 * reference count on the block.
5360 * when wc->stage == UPDATE_BACKREF, this function changes
5361 * wc->stage back to DROP_REFERENCE if we changed wc->stage
5362 * to UPDATE_BACKREF previously while processing the block.
5364 * NOTE: return value 1 means we should stop walking up.
5366 static noinline
int walk_up_proc(struct btrfs_trans_handle
*trans
,
5367 struct btrfs_root
*root
,
5368 struct btrfs_path
*path
,
5369 struct walk_control
*wc
)
5371 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
5373 int level
= wc
->level
;
5374 struct extent_buffer
*eb
= path
->nodes
[level
];
5377 if (wc
->stage
== UPDATE_BACKREF
) {
5378 BUG_ON(wc
->shared_level
< level
);
5379 if (level
< wc
->shared_level
)
5382 ret
= find_next_key(path
, level
+ 1, &wc
->update_progress
);
5386 wc
->stage
= DROP_REFERENCE
;
5387 wc
->shared_level
= -1;
5388 path
->slots
[level
] = 0;
5391 * check reference count again if the block isn't locked.
5392 * we should start walking down the tree again if reference
5395 if (!path
->locks
[level
]) {
5397 btrfs_tree_lock(eb
);
5398 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5400 ret
= btrfs_lookup_extent_info(trans
, fs_info
,
5401 eb
->start
, level
, 1,
5405 btrfs_tree_unlock_rw(eb
, path
->locks
[level
]);
5406 path
->locks
[level
] = 0;
5409 BUG_ON(wc
->refs
[level
] == 0);
5410 if (wc
->refs
[level
] == 1) {
5411 btrfs_tree_unlock_rw(eb
, path
->locks
[level
]);
5412 path
->locks
[level
] = 0;
5418 /* wc->stage == DROP_REFERENCE */
5419 BUG_ON(wc
->refs
[level
] > 1 && !path
->locks
[level
]);
5421 if (wc
->refs
[level
] == 1) {
5423 if (wc
->flags
[level
] & BTRFS_BLOCK_FLAG_FULL_BACKREF
)
5424 ret
= btrfs_dec_ref(trans
, root
, eb
, 1);
5426 ret
= btrfs_dec_ref(trans
, root
, eb
, 0);
5427 BUG_ON(ret
); /* -ENOMEM */
5428 if (is_fstree(root
->root_key
.objectid
)) {
5429 ret
= btrfs_qgroup_trace_leaf_items(trans
, eb
);
5431 btrfs_err_rl(fs_info
,
5432 "error %d accounting leaf items, quota is out of sync, rescan required",
5437 /* make block locked assertion in btrfs_clean_tree_block happy */
5438 if (!path
->locks
[level
] &&
5439 btrfs_header_generation(eb
) == trans
->transid
) {
5440 btrfs_tree_lock(eb
);
5441 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5443 btrfs_clean_tree_block(eb
);
5446 if (eb
== root
->node
) {
5447 if (wc
->flags
[level
] & BTRFS_BLOCK_FLAG_FULL_BACKREF
)
5449 else if (root
->root_key
.objectid
!= btrfs_header_owner(eb
))
5450 goto owner_mismatch
;
5452 if (wc
->flags
[level
+ 1] & BTRFS_BLOCK_FLAG_FULL_BACKREF
)
5453 parent
= path
->nodes
[level
+ 1]->start
;
5454 else if (root
->root_key
.objectid
!=
5455 btrfs_header_owner(path
->nodes
[level
+ 1]))
5456 goto owner_mismatch
;
5459 btrfs_free_tree_block(trans
, btrfs_root_id(root
), eb
, parent
,
5460 wc
->refs
[level
] == 1);
5462 wc
->refs
[level
] = 0;
5463 wc
->flags
[level
] = 0;
5467 btrfs_err_rl(fs_info
, "unexpected tree owner, have %llu expect %llu",
5468 btrfs_header_owner(eb
), root
->root_key
.objectid
);
5472 static noinline
int walk_down_tree(struct btrfs_trans_handle
*trans
,
5473 struct btrfs_root
*root
,
5474 struct btrfs_path
*path
,
5475 struct walk_control
*wc
)
5477 int level
= wc
->level
;
5478 int lookup_info
= 1;
5481 while (level
>= 0) {
5482 ret
= walk_down_proc(trans
, root
, path
, wc
, lookup_info
);
5489 if (path
->slots
[level
] >=
5490 btrfs_header_nritems(path
->nodes
[level
]))
5493 ret
= do_walk_down(trans
, root
, path
, wc
, &lookup_info
);
5495 path
->slots
[level
]++;
5504 static noinline
int walk_up_tree(struct btrfs_trans_handle
*trans
,
5505 struct btrfs_root
*root
,
5506 struct btrfs_path
*path
,
5507 struct walk_control
*wc
, int max_level
)
5509 int level
= wc
->level
;
5512 path
->slots
[level
] = btrfs_header_nritems(path
->nodes
[level
]);
5513 while (level
< max_level
&& path
->nodes
[level
]) {
5515 if (path
->slots
[level
] + 1 <
5516 btrfs_header_nritems(path
->nodes
[level
])) {
5517 path
->slots
[level
]++;
5520 ret
= walk_up_proc(trans
, root
, path
, wc
);
5526 if (path
->locks
[level
]) {
5527 btrfs_tree_unlock_rw(path
->nodes
[level
],
5528 path
->locks
[level
]);
5529 path
->locks
[level
] = 0;
5531 free_extent_buffer(path
->nodes
[level
]);
5532 path
->nodes
[level
] = NULL
;
5540 * drop a subvolume tree.
5542 * this function traverses the tree freeing any blocks that only
5543 * referenced by the tree.
5545 * when a shared tree block is found. this function decreases its
5546 * reference count by one. if update_ref is true, this function
5547 * also make sure backrefs for the shared block and all lower level
5548 * blocks are properly updated.
5550 * If called with for_reloc == 0, may exit early with -EAGAIN
5552 int btrfs_drop_snapshot(struct btrfs_root
*root
, int update_ref
, int for_reloc
)
5554 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
5555 struct btrfs_path
*path
;
5556 struct btrfs_trans_handle
*trans
;
5557 struct btrfs_root
*tree_root
= fs_info
->tree_root
;
5558 struct btrfs_root_item
*root_item
= &root
->root_item
;
5559 struct walk_control
*wc
;
5560 struct btrfs_key key
;
5564 bool root_dropped
= false;
5565 bool unfinished_drop
= false;
5567 btrfs_debug(fs_info
, "Drop subvolume %llu", root
->root_key
.objectid
);
5569 path
= btrfs_alloc_path();
5575 wc
= kzalloc(sizeof(*wc
), GFP_NOFS
);
5577 btrfs_free_path(path
);
5583 * Use join to avoid potential EINTR from transaction start. See
5584 * wait_reserve_ticket and the whole reservation callchain.
5587 trans
= btrfs_join_transaction(tree_root
);
5589 trans
= btrfs_start_transaction(tree_root
, 0);
5590 if (IS_ERR(trans
)) {
5591 err
= PTR_ERR(trans
);
5595 err
= btrfs_run_delayed_items(trans
);
5600 * This will help us catch people modifying the fs tree while we're
5601 * dropping it. It is unsafe to mess with the fs tree while it's being
5602 * dropped as we unlock the root node and parent nodes as we walk down
5603 * the tree, assuming nothing will change. If something does change
5604 * then we'll have stale information and drop references to blocks we've
5607 set_bit(BTRFS_ROOT_DELETING
, &root
->state
);
5608 unfinished_drop
= test_bit(BTRFS_ROOT_UNFINISHED_DROP
, &root
->state
);
5610 if (btrfs_disk_key_objectid(&root_item
->drop_progress
) == 0) {
5611 level
= btrfs_header_level(root
->node
);
5612 path
->nodes
[level
] = btrfs_lock_root_node(root
);
5613 path
->slots
[level
] = 0;
5614 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5615 memset(&wc
->update_progress
, 0,
5616 sizeof(wc
->update_progress
));
5618 btrfs_disk_key_to_cpu(&key
, &root_item
->drop_progress
);
5619 memcpy(&wc
->update_progress
, &key
,
5620 sizeof(wc
->update_progress
));
5622 level
= btrfs_root_drop_level(root_item
);
5624 path
->lowest_level
= level
;
5625 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
5626 path
->lowest_level
= 0;
5634 * unlock our path, this is safe because only this
5635 * function is allowed to delete this snapshot
5637 btrfs_unlock_up_safe(path
, 0);
5639 level
= btrfs_header_level(root
->node
);
5641 btrfs_tree_lock(path
->nodes
[level
]);
5642 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5644 ret
= btrfs_lookup_extent_info(trans
, fs_info
,
5645 path
->nodes
[level
]->start
,
5646 level
, 1, &wc
->refs
[level
],
5652 BUG_ON(wc
->refs
[level
] == 0);
5654 if (level
== btrfs_root_drop_level(root_item
))
5657 btrfs_tree_unlock(path
->nodes
[level
]);
5658 path
->locks
[level
] = 0;
5659 WARN_ON(wc
->refs
[level
] != 1);
5664 wc
->restarted
= test_bit(BTRFS_ROOT_DEAD_TREE
, &root
->state
);
5666 wc
->shared_level
= -1;
5667 wc
->stage
= DROP_REFERENCE
;
5668 wc
->update_ref
= update_ref
;
5670 wc
->reada_count
= BTRFS_NODEPTRS_PER_BLOCK(fs_info
);
5674 ret
= walk_down_tree(trans
, root
, path
, wc
);
5680 ret
= walk_up_tree(trans
, root
, path
, wc
, BTRFS_MAX_LEVEL
);
5687 BUG_ON(wc
->stage
!= DROP_REFERENCE
);
5691 if (wc
->stage
== DROP_REFERENCE
) {
5692 wc
->drop_level
= wc
->level
;
5693 btrfs_node_key_to_cpu(path
->nodes
[wc
->drop_level
],
5695 path
->slots
[wc
->drop_level
]);
5697 btrfs_cpu_key_to_disk(&root_item
->drop_progress
,
5698 &wc
->drop_progress
);
5699 btrfs_set_root_drop_level(root_item
, wc
->drop_level
);
5701 BUG_ON(wc
->level
== 0);
5702 if (btrfs_should_end_transaction(trans
) ||
5703 (!for_reloc
&& btrfs_need_cleaner_sleep(fs_info
))) {
5704 ret
= btrfs_update_root(trans
, tree_root
,
5708 btrfs_abort_transaction(trans
, ret
);
5713 btrfs_end_transaction_throttle(trans
);
5714 if (!for_reloc
&& btrfs_need_cleaner_sleep(fs_info
)) {
5715 btrfs_debug(fs_info
,
5716 "drop snapshot early exit");
5722 * Use join to avoid potential EINTR from transaction
5723 * start. See wait_reserve_ticket and the whole
5724 * reservation callchain.
5727 trans
= btrfs_join_transaction(tree_root
);
5729 trans
= btrfs_start_transaction(tree_root
, 0);
5730 if (IS_ERR(trans
)) {
5731 err
= PTR_ERR(trans
);
5736 btrfs_release_path(path
);
5740 ret
= btrfs_del_root(trans
, &root
->root_key
);
5742 btrfs_abort_transaction(trans
, ret
);
5747 if (root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
) {
5748 ret
= btrfs_find_root(tree_root
, &root
->root_key
, path
,
5751 btrfs_abort_transaction(trans
, ret
);
5754 } else if (ret
> 0) {
5755 /* if we fail to delete the orphan item this time
5756 * around, it'll get picked up the next time.
5758 * The most common failure here is just -ENOENT.
5760 btrfs_del_orphan_item(trans
, tree_root
,
5761 root
->root_key
.objectid
);
5766 * This subvolume is going to be completely dropped, and won't be
5767 * recorded as dirty roots, thus pertrans meta rsv will not be freed at
5768 * commit transaction time. So free it here manually.
5770 btrfs_qgroup_convert_reserved_meta(root
, INT_MAX
);
5771 btrfs_qgroup_free_meta_all_pertrans(root
);
5773 if (test_bit(BTRFS_ROOT_IN_RADIX
, &root
->state
))
5774 btrfs_add_dropped_root(trans
, root
);
5776 btrfs_put_root(root
);
5777 root_dropped
= true;
5779 btrfs_end_transaction_throttle(trans
);
5782 btrfs_free_path(path
);
5785 * We were an unfinished drop root, check to see if there are any
5786 * pending, and if not clear and wake up any waiters.
5788 if (!err
&& unfinished_drop
)
5789 btrfs_maybe_wake_unfinished_drop(fs_info
);
5792 * So if we need to stop dropping the snapshot for whatever reason we
5793 * need to make sure to add it back to the dead root list so that we
5794 * keep trying to do the work later. This also cleans up roots if we
5795 * don't have it in the radix (like when we recover after a power fail
5796 * or unmount) so we don't leak memory.
5798 if (!for_reloc
&& !root_dropped
)
5799 btrfs_add_dead_root(root
);
5804 * drop subtree rooted at tree block 'node'.
5806 * NOTE: this function will unlock and release tree block 'node'
5807 * only used by relocation code
5809 int btrfs_drop_subtree(struct btrfs_trans_handle
*trans
,
5810 struct btrfs_root
*root
,
5811 struct extent_buffer
*node
,
5812 struct extent_buffer
*parent
)
5814 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
5815 struct btrfs_path
*path
;
5816 struct walk_control
*wc
;
5822 BUG_ON(root
->root_key
.objectid
!= BTRFS_TREE_RELOC_OBJECTID
);
5824 path
= btrfs_alloc_path();
5828 wc
= kzalloc(sizeof(*wc
), GFP_NOFS
);
5830 btrfs_free_path(path
);
5834 btrfs_assert_tree_locked(parent
);
5835 parent_level
= btrfs_header_level(parent
);
5836 atomic_inc(&parent
->refs
);
5837 path
->nodes
[parent_level
] = parent
;
5838 path
->slots
[parent_level
] = btrfs_header_nritems(parent
);
5840 btrfs_assert_tree_locked(node
);
5841 level
= btrfs_header_level(node
);
5842 path
->nodes
[level
] = node
;
5843 path
->slots
[level
] = 0;
5844 path
->locks
[level
] = BTRFS_WRITE_LOCK
;
5846 wc
->refs
[parent_level
] = 1;
5847 wc
->flags
[parent_level
] = BTRFS_BLOCK_FLAG_FULL_BACKREF
;
5849 wc
->shared_level
= -1;
5850 wc
->stage
= DROP_REFERENCE
;
5853 wc
->reada_count
= BTRFS_NODEPTRS_PER_BLOCK(fs_info
);
5856 wret
= walk_down_tree(trans
, root
, path
, wc
);
5862 wret
= walk_up_tree(trans
, root
, path
, wc
, parent_level
);
5870 btrfs_free_path(path
);
5875 * helper to account the unused space of all the readonly block group in the
5876 * space_info. takes mirrors into account.
5878 u64
btrfs_account_ro_block_groups_free_space(struct btrfs_space_info
*sinfo
)
5880 struct btrfs_block_group
*block_group
;
5884 /* It's df, we don't care if it's racy */
5885 if (list_empty(&sinfo
->ro_bgs
))
5888 spin_lock(&sinfo
->lock
);
5889 list_for_each_entry(block_group
, &sinfo
->ro_bgs
, ro_list
) {
5890 spin_lock(&block_group
->lock
);
5892 if (!block_group
->ro
) {
5893 spin_unlock(&block_group
->lock
);
5897 factor
= btrfs_bg_type_to_factor(block_group
->flags
);
5898 free_bytes
+= (block_group
->length
-
5899 block_group
->used
) * factor
;
5901 spin_unlock(&block_group
->lock
);
5903 spin_unlock(&sinfo
->lock
);
5908 int btrfs_error_unpin_extent_range(struct btrfs_fs_info
*fs_info
,
5911 return unpin_extent_range(fs_info
, start
, end
, false);
5915 * It used to be that old block groups would be left around forever.
5916 * Iterating over them would be enough to trim unused space. Since we
5917 * now automatically remove them, we also need to iterate over unallocated
5920 * We don't want a transaction for this since the discard may take a
5921 * substantial amount of time. We don't require that a transaction be
5922 * running, but we do need to take a running transaction into account
5923 * to ensure that we're not discarding chunks that were released or
5924 * allocated in the current transaction.
5926 * Holding the chunks lock will prevent other threads from allocating
5927 * or releasing chunks, but it won't prevent a running transaction
5928 * from committing and releasing the memory that the pending chunks
5929 * list head uses. For that, we need to take a reference to the
5930 * transaction and hold the commit root sem. We only need to hold
5931 * it while performing the free space search since we have already
5932 * held back allocations.
5934 static int btrfs_trim_free_extents(struct btrfs_device
*device
, u64
*trimmed
)
5936 u64 start
= SZ_1M
, len
= 0, end
= 0;
5941 /* Discard not supported = nothing to do. */
5942 if (!blk_queue_discard(bdev_get_queue(device
->bdev
)))
5945 /* Not writable = nothing to do. */
5946 if (!test_bit(BTRFS_DEV_STATE_WRITEABLE
, &device
->dev_state
))
5949 /* No free space = nothing to do. */
5950 if (device
->total_bytes
<= device
->bytes_used
)
5956 struct btrfs_fs_info
*fs_info
= device
->fs_info
;
5959 ret
= mutex_lock_interruptible(&fs_info
->chunk_mutex
);
5963 find_first_clear_extent_bit(&device
->alloc_state
, start
,
5965 CHUNK_TRIMMED
| CHUNK_ALLOCATED
);
5967 /* Check if there are any CHUNK_* bits left */
5968 if (start
> device
->total_bytes
) {
5969 WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG
));
5970 btrfs_warn_in_rcu(fs_info
,
5971 "ignoring attempt to trim beyond device size: offset %llu length %llu device %s device size %llu",
5972 start
, end
- start
+ 1,
5973 rcu_str_deref(device
->name
),
5974 device
->total_bytes
);
5975 mutex_unlock(&fs_info
->chunk_mutex
);
5980 /* Ensure we skip the reserved area in the first 1M */
5981 start
= max_t(u64
, start
, SZ_1M
);
5984 * If find_first_clear_extent_bit find a range that spans the
5985 * end of the device it will set end to -1, in this case it's up
5986 * to the caller to trim the value to the size of the device.
5988 end
= min(end
, device
->total_bytes
- 1);
5990 len
= end
- start
+ 1;
5992 /* We didn't find any extents */
5994 mutex_unlock(&fs_info
->chunk_mutex
);
5999 ret
= btrfs_issue_discard(device
->bdev
, start
, len
,
6002 set_extent_bits(&device
->alloc_state
, start
,
6005 mutex_unlock(&fs_info
->chunk_mutex
);
6013 if (fatal_signal_pending(current
)) {
6025 * Trim the whole filesystem by:
6026 * 1) trimming the free space in each block group
6027 * 2) trimming the unallocated space on each device
6029 * This will also continue trimming even if a block group or device encounters
6030 * an error. The return value will be the last error, or 0 if nothing bad
6033 int btrfs_trim_fs(struct btrfs_fs_info
*fs_info
, struct fstrim_range
*range
)
6035 struct btrfs_fs_devices
*fs_devices
= fs_info
->fs_devices
;
6036 struct btrfs_block_group
*cache
= NULL
;
6037 struct btrfs_device
*device
;
6039 u64 range_end
= U64_MAX
;
6050 * Check range overflow if range->len is set.
6051 * The default range->len is U64_MAX.
6053 if (range
->len
!= U64_MAX
&&
6054 check_add_overflow(range
->start
, range
->len
, &range_end
))
6057 cache
= btrfs_lookup_first_block_group(fs_info
, range
->start
);
6058 for (; cache
; cache
= btrfs_next_block_group(cache
)) {
6059 if (cache
->start
>= range_end
) {
6060 btrfs_put_block_group(cache
);
6064 start
= max(range
->start
, cache
->start
);
6065 end
= min(range_end
, cache
->start
+ cache
->length
);
6067 if (end
- start
>= range
->minlen
) {
6068 if (!btrfs_block_group_done(cache
)) {
6069 ret
= btrfs_cache_block_group(cache
, 0);
6075 ret
= btrfs_wait_block_group_cache_done(cache
);
6082 ret
= btrfs_trim_block_group(cache
,
6088 trimmed
+= group_trimmed
;
6099 "failed to trim %llu block group(s), last error %d",
6102 mutex_lock(&fs_devices
->device_list_mutex
);
6103 list_for_each_entry(device
, &fs_devices
->devices
, dev_list
) {
6104 if (test_bit(BTRFS_DEV_STATE_MISSING
, &device
->dev_state
))
6107 ret
= btrfs_trim_free_extents(device
, &group_trimmed
);
6114 trimmed
+= group_trimmed
;
6116 mutex_unlock(&fs_devices
->device_list_mutex
);
6120 "failed to trim %llu device(s), last error %d",
6121 dev_failed
, dev_ret
);
6122 range
->len
= trimmed
;