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