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