1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2011 STRATO. All rights reserved. 4 */ 5 6 #include <linux/mm.h> 7 #include <linux/rbtree.h> 8 #include <trace/events/btrfs.h> 9 #include "ctree.h" 10 #include "disk-io.h" 11 #include "backref.h" 12 #include "ulist.h" 13 #include "transaction.h" 14 #include "delayed-ref.h" 15 #include "locking.h" 16 #include "misc.h" 17 #include "tree-mod-log.h" 18 19 /* Just an arbitrary number so we can be sure this happened */ 20 #define BACKREF_FOUND_SHARED 6 21 22 struct extent_inode_elem { 23 u64 inum; 24 u64 offset; 25 struct extent_inode_elem *next; 26 }; 27 28 static int check_extent_in_eb(const struct btrfs_key *key, 29 const struct extent_buffer *eb, 30 const struct btrfs_file_extent_item *fi, 31 u64 extent_item_pos, 32 struct extent_inode_elem **eie, 33 bool ignore_offset) 34 { 35 u64 offset = 0; 36 struct extent_inode_elem *e; 37 38 if (!ignore_offset && 39 !btrfs_file_extent_compression(eb, fi) && 40 !btrfs_file_extent_encryption(eb, fi) && 41 !btrfs_file_extent_other_encoding(eb, fi)) { 42 u64 data_offset; 43 u64 data_len; 44 45 data_offset = btrfs_file_extent_offset(eb, fi); 46 data_len = btrfs_file_extent_num_bytes(eb, fi); 47 48 if (extent_item_pos < data_offset || 49 extent_item_pos >= data_offset + data_len) 50 return 1; 51 offset = extent_item_pos - data_offset; 52 } 53 54 e = kmalloc(sizeof(*e), GFP_NOFS); 55 if (!e) 56 return -ENOMEM; 57 58 e->next = *eie; 59 e->inum = key->objectid; 60 e->offset = key->offset + offset; 61 *eie = e; 62 63 return 0; 64 } 65 66 static void free_inode_elem_list(struct extent_inode_elem *eie) 67 { 68 struct extent_inode_elem *eie_next; 69 70 for (; eie; eie = eie_next) { 71 eie_next = eie->next; 72 kfree(eie); 73 } 74 } 75 76 static int find_extent_in_eb(const struct extent_buffer *eb, 77 u64 wanted_disk_byte, u64 extent_item_pos, 78 struct extent_inode_elem **eie, 79 bool ignore_offset) 80 { 81 u64 disk_byte; 82 struct btrfs_key key; 83 struct btrfs_file_extent_item *fi; 84 int slot; 85 int nritems; 86 int extent_type; 87 int ret; 88 89 /* 90 * from the shared data ref, we only have the leaf but we need 91 * the key. thus, we must look into all items and see that we 92 * find one (some) with a reference to our extent item. 93 */ 94 nritems = btrfs_header_nritems(eb); 95 for (slot = 0; slot < nritems; ++slot) { 96 btrfs_item_key_to_cpu(eb, &key, slot); 97 if (key.type != BTRFS_EXTENT_DATA_KEY) 98 continue; 99 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 100 extent_type = btrfs_file_extent_type(eb, fi); 101 if (extent_type == BTRFS_FILE_EXTENT_INLINE) 102 continue; 103 /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */ 104 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi); 105 if (disk_byte != wanted_disk_byte) 106 continue; 107 108 ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie, ignore_offset); 109 if (ret < 0) 110 return ret; 111 } 112 113 return 0; 114 } 115 116 struct preftree { 117 struct rb_root_cached root; 118 unsigned int count; 119 }; 120 121 #define PREFTREE_INIT { .root = RB_ROOT_CACHED, .count = 0 } 122 123 struct preftrees { 124 struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */ 125 struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */ 126 struct preftree indirect_missing_keys; 127 }; 128 129 /* 130 * Checks for a shared extent during backref search. 131 * 132 * The share_count tracks prelim_refs (direct and indirect) having a 133 * ref->count >0: 134 * - incremented when a ref->count transitions to >0 135 * - decremented when a ref->count transitions to <1 136 */ 137 struct share_check { 138 u64 root_objectid; 139 u64 inum; 140 int share_count; 141 }; 142 143 static inline int extent_is_shared(struct share_check *sc) 144 { 145 return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0; 146 } 147 148 static struct kmem_cache *btrfs_prelim_ref_cache; 149 150 int __init btrfs_prelim_ref_init(void) 151 { 152 btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref", 153 sizeof(struct prelim_ref), 154 0, 155 SLAB_MEM_SPREAD, 156 NULL); 157 if (!btrfs_prelim_ref_cache) 158 return -ENOMEM; 159 return 0; 160 } 161 162 void __cold btrfs_prelim_ref_exit(void) 163 { 164 kmem_cache_destroy(btrfs_prelim_ref_cache); 165 } 166 167 static void free_pref(struct prelim_ref *ref) 168 { 169 kmem_cache_free(btrfs_prelim_ref_cache, ref); 170 } 171 172 /* 173 * Return 0 when both refs are for the same block (and can be merged). 174 * A -1 return indicates ref1 is a 'lower' block than ref2, while 1 175 * indicates a 'higher' block. 176 */ 177 static int prelim_ref_compare(struct prelim_ref *ref1, 178 struct prelim_ref *ref2) 179 { 180 if (ref1->level < ref2->level) 181 return -1; 182 if (ref1->level > ref2->level) 183 return 1; 184 if (ref1->root_id < ref2->root_id) 185 return -1; 186 if (ref1->root_id > ref2->root_id) 187 return 1; 188 if (ref1->key_for_search.type < ref2->key_for_search.type) 189 return -1; 190 if (ref1->key_for_search.type > ref2->key_for_search.type) 191 return 1; 192 if (ref1->key_for_search.objectid < ref2->key_for_search.objectid) 193 return -1; 194 if (ref1->key_for_search.objectid > ref2->key_for_search.objectid) 195 return 1; 196 if (ref1->key_for_search.offset < ref2->key_for_search.offset) 197 return -1; 198 if (ref1->key_for_search.offset > ref2->key_for_search.offset) 199 return 1; 200 if (ref1->parent < ref2->parent) 201 return -1; 202 if (ref1->parent > ref2->parent) 203 return 1; 204 205 return 0; 206 } 207 208 static void update_share_count(struct share_check *sc, int oldcount, 209 int newcount) 210 { 211 if ((!sc) || (oldcount == 0 && newcount < 1)) 212 return; 213 214 if (oldcount > 0 && newcount < 1) 215 sc->share_count--; 216 else if (oldcount < 1 && newcount > 0) 217 sc->share_count++; 218 } 219 220 /* 221 * Add @newref to the @root rbtree, merging identical refs. 222 * 223 * Callers should assume that newref has been freed after calling. 224 */ 225 static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, 226 struct preftree *preftree, 227 struct prelim_ref *newref, 228 struct share_check *sc) 229 { 230 struct rb_root_cached *root; 231 struct rb_node **p; 232 struct rb_node *parent = NULL; 233 struct prelim_ref *ref; 234 int result; 235 bool leftmost = true; 236 237 root = &preftree->root; 238 p = &root->rb_root.rb_node; 239 240 while (*p) { 241 parent = *p; 242 ref = rb_entry(parent, struct prelim_ref, rbnode); 243 result = prelim_ref_compare(ref, newref); 244 if (result < 0) { 245 p = &(*p)->rb_left; 246 } else if (result > 0) { 247 p = &(*p)->rb_right; 248 leftmost = false; 249 } else { 250 /* Identical refs, merge them and free @newref */ 251 struct extent_inode_elem *eie = ref->inode_list; 252 253 while (eie && eie->next) 254 eie = eie->next; 255 256 if (!eie) 257 ref->inode_list = newref->inode_list; 258 else 259 eie->next = newref->inode_list; 260 trace_btrfs_prelim_ref_merge(fs_info, ref, newref, 261 preftree->count); 262 /* 263 * A delayed ref can have newref->count < 0. 264 * The ref->count is updated to follow any 265 * BTRFS_[ADD|DROP]_DELAYED_REF actions. 266 */ 267 update_share_count(sc, ref->count, 268 ref->count + newref->count); 269 ref->count += newref->count; 270 free_pref(newref); 271 return; 272 } 273 } 274 275 update_share_count(sc, 0, newref->count); 276 preftree->count++; 277 trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count); 278 rb_link_node(&newref->rbnode, parent, p); 279 rb_insert_color_cached(&newref->rbnode, root, leftmost); 280 } 281 282 /* 283 * Release the entire tree. We don't care about internal consistency so 284 * just free everything and then reset the tree root. 285 */ 286 static void prelim_release(struct preftree *preftree) 287 { 288 struct prelim_ref *ref, *next_ref; 289 290 rbtree_postorder_for_each_entry_safe(ref, next_ref, 291 &preftree->root.rb_root, rbnode) 292 free_pref(ref); 293 294 preftree->root = RB_ROOT_CACHED; 295 preftree->count = 0; 296 } 297 298 /* 299 * the rules for all callers of this function are: 300 * - obtaining the parent is the goal 301 * - if you add a key, you must know that it is a correct key 302 * - if you cannot add the parent or a correct key, then we will look into the 303 * block later to set a correct key 304 * 305 * delayed refs 306 * ============ 307 * backref type | shared | indirect | shared | indirect 308 * information | tree | tree | data | data 309 * --------------------+--------+----------+--------+---------- 310 * parent logical | y | - | - | - 311 * key to resolve | - | y | y | y 312 * tree block logical | - | - | - | - 313 * root for resolving | y | y | y | y 314 * 315 * - column 1: we've the parent -> done 316 * - column 2, 3, 4: we use the key to find the parent 317 * 318 * on disk refs (inline or keyed) 319 * ============================== 320 * backref type | shared | indirect | shared | indirect 321 * information | tree | tree | data | data 322 * --------------------+--------+----------+--------+---------- 323 * parent logical | y | - | y | - 324 * key to resolve | - | - | - | y 325 * tree block logical | y | y | y | y 326 * root for resolving | - | y | y | y 327 * 328 * - column 1, 3: we've the parent -> done 329 * - column 2: we take the first key from the block to find the parent 330 * (see add_missing_keys) 331 * - column 4: we use the key to find the parent 332 * 333 * additional information that's available but not required to find the parent 334 * block might help in merging entries to gain some speed. 335 */ 336 static int add_prelim_ref(const struct btrfs_fs_info *fs_info, 337 struct preftree *preftree, u64 root_id, 338 const struct btrfs_key *key, int level, u64 parent, 339 u64 wanted_disk_byte, int count, 340 struct share_check *sc, gfp_t gfp_mask) 341 { 342 struct prelim_ref *ref; 343 344 if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID) 345 return 0; 346 347 ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask); 348 if (!ref) 349 return -ENOMEM; 350 351 ref->root_id = root_id; 352 if (key) 353 ref->key_for_search = *key; 354 else 355 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search)); 356 357 ref->inode_list = NULL; 358 ref->level = level; 359 ref->count = count; 360 ref->parent = parent; 361 ref->wanted_disk_byte = wanted_disk_byte; 362 prelim_ref_insert(fs_info, preftree, ref, sc); 363 return extent_is_shared(sc); 364 } 365 366 /* direct refs use root == 0, key == NULL */ 367 static int add_direct_ref(const struct btrfs_fs_info *fs_info, 368 struct preftrees *preftrees, int level, u64 parent, 369 u64 wanted_disk_byte, int count, 370 struct share_check *sc, gfp_t gfp_mask) 371 { 372 return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level, 373 parent, wanted_disk_byte, count, sc, gfp_mask); 374 } 375 376 /* indirect refs use parent == 0 */ 377 static int add_indirect_ref(const struct btrfs_fs_info *fs_info, 378 struct preftrees *preftrees, u64 root_id, 379 const struct btrfs_key *key, int level, 380 u64 wanted_disk_byte, int count, 381 struct share_check *sc, gfp_t gfp_mask) 382 { 383 struct preftree *tree = &preftrees->indirect; 384 385 if (!key) 386 tree = &preftrees->indirect_missing_keys; 387 return add_prelim_ref(fs_info, tree, root_id, key, level, 0, 388 wanted_disk_byte, count, sc, gfp_mask); 389 } 390 391 static int is_shared_data_backref(struct preftrees *preftrees, u64 bytenr) 392 { 393 struct rb_node **p = &preftrees->direct.root.rb_root.rb_node; 394 struct rb_node *parent = NULL; 395 struct prelim_ref *ref = NULL; 396 struct prelim_ref target = {}; 397 int result; 398 399 target.parent = bytenr; 400 401 while (*p) { 402 parent = *p; 403 ref = rb_entry(parent, struct prelim_ref, rbnode); 404 result = prelim_ref_compare(ref, &target); 405 406 if (result < 0) 407 p = &(*p)->rb_left; 408 else if (result > 0) 409 p = &(*p)->rb_right; 410 else 411 return 1; 412 } 413 return 0; 414 } 415 416 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, 417 struct ulist *parents, 418 struct preftrees *preftrees, struct prelim_ref *ref, 419 int level, u64 time_seq, const u64 *extent_item_pos, 420 bool ignore_offset) 421 { 422 int ret = 0; 423 int slot; 424 struct extent_buffer *eb; 425 struct btrfs_key key; 426 struct btrfs_key *key_for_search = &ref->key_for_search; 427 struct btrfs_file_extent_item *fi; 428 struct extent_inode_elem *eie = NULL, *old = NULL; 429 u64 disk_byte; 430 u64 wanted_disk_byte = ref->wanted_disk_byte; 431 u64 count = 0; 432 u64 data_offset; 433 434 if (level != 0) { 435 eb = path->nodes[level]; 436 ret = ulist_add(parents, eb->start, 0, GFP_NOFS); 437 if (ret < 0) 438 return ret; 439 return 0; 440 } 441 442 /* 443 * 1. We normally enter this function with the path already pointing to 444 * the first item to check. But sometimes, we may enter it with 445 * slot == nritems. 446 * 2. We are searching for normal backref but bytenr of this leaf 447 * matches shared data backref 448 * 3. The leaf owner is not equal to the root we are searching 449 * 450 * For these cases, go to the next leaf before we continue. 451 */ 452 eb = path->nodes[0]; 453 if (path->slots[0] >= btrfs_header_nritems(eb) || 454 is_shared_data_backref(preftrees, eb->start) || 455 ref->root_id != btrfs_header_owner(eb)) { 456 if (time_seq == BTRFS_SEQ_LAST) 457 ret = btrfs_next_leaf(root, path); 458 else 459 ret = btrfs_next_old_leaf(root, path, time_seq); 460 } 461 462 while (!ret && count < ref->count) { 463 eb = path->nodes[0]; 464 slot = path->slots[0]; 465 466 btrfs_item_key_to_cpu(eb, &key, slot); 467 468 if (key.objectid != key_for_search->objectid || 469 key.type != BTRFS_EXTENT_DATA_KEY) 470 break; 471 472 /* 473 * We are searching for normal backref but bytenr of this leaf 474 * matches shared data backref, OR 475 * the leaf owner is not equal to the root we are searching for 476 */ 477 if (slot == 0 && 478 (is_shared_data_backref(preftrees, eb->start) || 479 ref->root_id != btrfs_header_owner(eb))) { 480 if (time_seq == BTRFS_SEQ_LAST) 481 ret = btrfs_next_leaf(root, path); 482 else 483 ret = btrfs_next_old_leaf(root, path, time_seq); 484 continue; 485 } 486 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 487 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi); 488 data_offset = btrfs_file_extent_offset(eb, fi); 489 490 if (disk_byte == wanted_disk_byte) { 491 eie = NULL; 492 old = NULL; 493 if (ref->key_for_search.offset == key.offset - data_offset) 494 count++; 495 else 496 goto next; 497 if (extent_item_pos) { 498 ret = check_extent_in_eb(&key, eb, fi, 499 *extent_item_pos, 500 &eie, ignore_offset); 501 if (ret < 0) 502 break; 503 } 504 if (ret > 0) 505 goto next; 506 ret = ulist_add_merge_ptr(parents, eb->start, 507 eie, (void **)&old, GFP_NOFS); 508 if (ret < 0) 509 break; 510 if (!ret && extent_item_pos) { 511 while (old->next) 512 old = old->next; 513 old->next = eie; 514 } 515 eie = NULL; 516 } 517 next: 518 if (time_seq == BTRFS_SEQ_LAST) 519 ret = btrfs_next_item(root, path); 520 else 521 ret = btrfs_next_old_item(root, path, time_seq); 522 } 523 524 if (ret > 0) 525 ret = 0; 526 else if (ret < 0) 527 free_inode_elem_list(eie); 528 return ret; 529 } 530 531 /* 532 * resolve an indirect backref in the form (root_id, key, level) 533 * to a logical address 534 */ 535 static int resolve_indirect_ref(struct btrfs_fs_info *fs_info, 536 struct btrfs_path *path, u64 time_seq, 537 struct preftrees *preftrees, 538 struct prelim_ref *ref, struct ulist *parents, 539 const u64 *extent_item_pos, bool ignore_offset) 540 { 541 struct btrfs_root *root; 542 struct extent_buffer *eb; 543 int ret = 0; 544 int root_level; 545 int level = ref->level; 546 struct btrfs_key search_key = ref->key_for_search; 547 548 /* 549 * If we're search_commit_root we could possibly be holding locks on 550 * other tree nodes. This happens when qgroups does backref walks when 551 * adding new delayed refs. To deal with this we need to look in cache 552 * for the root, and if we don't find it then we need to search the 553 * tree_root's commit root, thus the btrfs_get_fs_root_commit_root usage 554 * here. 555 */ 556 if (path->search_commit_root) 557 root = btrfs_get_fs_root_commit_root(fs_info, path, ref->root_id); 558 else 559 root = btrfs_get_fs_root(fs_info, ref->root_id, false); 560 if (IS_ERR(root)) { 561 ret = PTR_ERR(root); 562 goto out_free; 563 } 564 565 if (!path->search_commit_root && 566 test_bit(BTRFS_ROOT_DELETING, &root->state)) { 567 ret = -ENOENT; 568 goto out; 569 } 570 571 if (btrfs_is_testing(fs_info)) { 572 ret = -ENOENT; 573 goto out; 574 } 575 576 if (path->search_commit_root) 577 root_level = btrfs_header_level(root->commit_root); 578 else if (time_seq == BTRFS_SEQ_LAST) 579 root_level = btrfs_header_level(root->node); 580 else 581 root_level = btrfs_old_root_level(root, time_seq); 582 583 if (root_level + 1 == level) 584 goto out; 585 586 /* 587 * We can often find data backrefs with an offset that is too large 588 * (>= LLONG_MAX, maximum allowed file offset) due to underflows when 589 * subtracting a file's offset with the data offset of its 590 * corresponding extent data item. This can happen for example in the 591 * clone ioctl. 592 * 593 * So if we detect such case we set the search key's offset to zero to 594 * make sure we will find the matching file extent item at 595 * add_all_parents(), otherwise we will miss it because the offset 596 * taken form the backref is much larger then the offset of the file 597 * extent item. This can make us scan a very large number of file 598 * extent items, but at least it will not make us miss any. 599 * 600 * This is an ugly workaround for a behaviour that should have never 601 * existed, but it does and a fix for the clone ioctl would touch a lot 602 * of places, cause backwards incompatibility and would not fix the 603 * problem for extents cloned with older kernels. 604 */ 605 if (search_key.type == BTRFS_EXTENT_DATA_KEY && 606 search_key.offset >= LLONG_MAX) 607 search_key.offset = 0; 608 path->lowest_level = level; 609 if (time_seq == BTRFS_SEQ_LAST) 610 ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0); 611 else 612 ret = btrfs_search_old_slot(root, &search_key, path, time_seq); 613 614 btrfs_debug(fs_info, 615 "search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)", 616 ref->root_id, level, ref->count, ret, 617 ref->key_for_search.objectid, ref->key_for_search.type, 618 ref->key_for_search.offset); 619 if (ret < 0) 620 goto out; 621 622 eb = path->nodes[level]; 623 while (!eb) { 624 if (WARN_ON(!level)) { 625 ret = 1; 626 goto out; 627 } 628 level--; 629 eb = path->nodes[level]; 630 } 631 632 ret = add_all_parents(root, path, parents, preftrees, ref, level, 633 time_seq, extent_item_pos, ignore_offset); 634 out: 635 btrfs_put_root(root); 636 out_free: 637 path->lowest_level = 0; 638 btrfs_release_path(path); 639 return ret; 640 } 641 642 static struct extent_inode_elem * 643 unode_aux_to_inode_list(struct ulist_node *node) 644 { 645 if (!node) 646 return NULL; 647 return (struct extent_inode_elem *)(uintptr_t)node->aux; 648 } 649 650 /* 651 * We maintain three separate rbtrees: one for direct refs, one for 652 * indirect refs which have a key, and one for indirect refs which do not 653 * have a key. Each tree does merge on insertion. 654 * 655 * Once all of the references are located, we iterate over the tree of 656 * indirect refs with missing keys. An appropriate key is located and 657 * the ref is moved onto the tree for indirect refs. After all missing 658 * keys are thus located, we iterate over the indirect ref tree, resolve 659 * each reference, and then insert the resolved reference onto the 660 * direct tree (merging there too). 661 * 662 * New backrefs (i.e., for parent nodes) are added to the appropriate 663 * rbtree as they are encountered. The new backrefs are subsequently 664 * resolved as above. 665 */ 666 static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, 667 struct btrfs_path *path, u64 time_seq, 668 struct preftrees *preftrees, 669 const u64 *extent_item_pos, 670 struct share_check *sc, bool ignore_offset) 671 { 672 int err; 673 int ret = 0; 674 struct ulist *parents; 675 struct ulist_node *node; 676 struct ulist_iterator uiter; 677 struct rb_node *rnode; 678 679 parents = ulist_alloc(GFP_NOFS); 680 if (!parents) 681 return -ENOMEM; 682 683 /* 684 * We could trade memory usage for performance here by iterating 685 * the tree, allocating new refs for each insertion, and then 686 * freeing the entire indirect tree when we're done. In some test 687 * cases, the tree can grow quite large (~200k objects). 688 */ 689 while ((rnode = rb_first_cached(&preftrees->indirect.root))) { 690 struct prelim_ref *ref; 691 692 ref = rb_entry(rnode, struct prelim_ref, rbnode); 693 if (WARN(ref->parent, 694 "BUG: direct ref found in indirect tree")) { 695 ret = -EINVAL; 696 goto out; 697 } 698 699 rb_erase_cached(&ref->rbnode, &preftrees->indirect.root); 700 preftrees->indirect.count--; 701 702 if (ref->count == 0) { 703 free_pref(ref); 704 continue; 705 } 706 707 if (sc && sc->root_objectid && 708 ref->root_id != sc->root_objectid) { 709 free_pref(ref); 710 ret = BACKREF_FOUND_SHARED; 711 goto out; 712 } 713 err = resolve_indirect_ref(fs_info, path, time_seq, preftrees, 714 ref, parents, extent_item_pos, 715 ignore_offset); 716 /* 717 * we can only tolerate ENOENT,otherwise,we should catch error 718 * and return directly. 719 */ 720 if (err == -ENOENT) { 721 prelim_ref_insert(fs_info, &preftrees->direct, ref, 722 NULL); 723 continue; 724 } else if (err) { 725 free_pref(ref); 726 ret = err; 727 goto out; 728 } 729 730 /* we put the first parent into the ref at hand */ 731 ULIST_ITER_INIT(&uiter); 732 node = ulist_next(parents, &uiter); 733 ref->parent = node ? node->val : 0; 734 ref->inode_list = unode_aux_to_inode_list(node); 735 736 /* Add a prelim_ref(s) for any other parent(s). */ 737 while ((node = ulist_next(parents, &uiter))) { 738 struct prelim_ref *new_ref; 739 740 new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache, 741 GFP_NOFS); 742 if (!new_ref) { 743 free_pref(ref); 744 ret = -ENOMEM; 745 goto out; 746 } 747 memcpy(new_ref, ref, sizeof(*ref)); 748 new_ref->parent = node->val; 749 new_ref->inode_list = unode_aux_to_inode_list(node); 750 prelim_ref_insert(fs_info, &preftrees->direct, 751 new_ref, NULL); 752 } 753 754 /* 755 * Now it's a direct ref, put it in the direct tree. We must 756 * do this last because the ref could be merged/freed here. 757 */ 758 prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL); 759 760 ulist_reinit(parents); 761 cond_resched(); 762 } 763 out: 764 ulist_free(parents); 765 return ret; 766 } 767 768 /* 769 * read tree blocks and add keys where required. 770 */ 771 static int add_missing_keys(struct btrfs_fs_info *fs_info, 772 struct preftrees *preftrees, bool lock) 773 { 774 struct prelim_ref *ref; 775 struct extent_buffer *eb; 776 struct preftree *tree = &preftrees->indirect_missing_keys; 777 struct rb_node *node; 778 779 while ((node = rb_first_cached(&tree->root))) { 780 ref = rb_entry(node, struct prelim_ref, rbnode); 781 rb_erase_cached(node, &tree->root); 782 783 BUG_ON(ref->parent); /* should not be a direct ref */ 784 BUG_ON(ref->key_for_search.type); 785 BUG_ON(!ref->wanted_disk_byte); 786 787 eb = read_tree_block(fs_info, ref->wanted_disk_byte, 788 ref->root_id, 0, ref->level - 1, NULL); 789 if (IS_ERR(eb)) { 790 free_pref(ref); 791 return PTR_ERR(eb); 792 } else if (!extent_buffer_uptodate(eb)) { 793 free_pref(ref); 794 free_extent_buffer(eb); 795 return -EIO; 796 } 797 if (lock) 798 btrfs_tree_read_lock(eb); 799 if (btrfs_header_level(eb) == 0) 800 btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0); 801 else 802 btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0); 803 if (lock) 804 btrfs_tree_read_unlock(eb); 805 free_extent_buffer(eb); 806 prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL); 807 cond_resched(); 808 } 809 return 0; 810 } 811 812 /* 813 * add all currently queued delayed refs from this head whose seq nr is 814 * smaller or equal that seq to the list 815 */ 816 static int add_delayed_refs(const struct btrfs_fs_info *fs_info, 817 struct btrfs_delayed_ref_head *head, u64 seq, 818 struct preftrees *preftrees, struct share_check *sc) 819 { 820 struct btrfs_delayed_ref_node *node; 821 struct btrfs_delayed_extent_op *extent_op = head->extent_op; 822 struct btrfs_key key; 823 struct btrfs_key tmp_op_key; 824 struct rb_node *n; 825 int count; 826 int ret = 0; 827 828 if (extent_op && extent_op->update_key) 829 btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key); 830 831 spin_lock(&head->lock); 832 for (n = rb_first_cached(&head->ref_tree); n; n = rb_next(n)) { 833 node = rb_entry(n, struct btrfs_delayed_ref_node, 834 ref_node); 835 if (node->seq > seq) 836 continue; 837 838 switch (node->action) { 839 case BTRFS_ADD_DELAYED_EXTENT: 840 case BTRFS_UPDATE_DELAYED_HEAD: 841 WARN_ON(1); 842 continue; 843 case BTRFS_ADD_DELAYED_REF: 844 count = node->ref_mod; 845 break; 846 case BTRFS_DROP_DELAYED_REF: 847 count = node->ref_mod * -1; 848 break; 849 default: 850 BUG(); 851 } 852 switch (node->type) { 853 case BTRFS_TREE_BLOCK_REF_KEY: { 854 /* NORMAL INDIRECT METADATA backref */ 855 struct btrfs_delayed_tree_ref *ref; 856 857 ref = btrfs_delayed_node_to_tree_ref(node); 858 ret = add_indirect_ref(fs_info, preftrees, ref->root, 859 &tmp_op_key, ref->level + 1, 860 node->bytenr, count, sc, 861 GFP_ATOMIC); 862 break; 863 } 864 case BTRFS_SHARED_BLOCK_REF_KEY: { 865 /* SHARED DIRECT METADATA backref */ 866 struct btrfs_delayed_tree_ref *ref; 867 868 ref = btrfs_delayed_node_to_tree_ref(node); 869 870 ret = add_direct_ref(fs_info, preftrees, ref->level + 1, 871 ref->parent, node->bytenr, count, 872 sc, GFP_ATOMIC); 873 break; 874 } 875 case BTRFS_EXTENT_DATA_REF_KEY: { 876 /* NORMAL INDIRECT DATA backref */ 877 struct btrfs_delayed_data_ref *ref; 878 ref = btrfs_delayed_node_to_data_ref(node); 879 880 key.objectid = ref->objectid; 881 key.type = BTRFS_EXTENT_DATA_KEY; 882 key.offset = ref->offset; 883 884 /* 885 * Found a inum that doesn't match our known inum, we 886 * know it's shared. 887 */ 888 if (sc && sc->inum && ref->objectid != sc->inum) { 889 ret = BACKREF_FOUND_SHARED; 890 goto out; 891 } 892 893 ret = add_indirect_ref(fs_info, preftrees, ref->root, 894 &key, 0, node->bytenr, count, sc, 895 GFP_ATOMIC); 896 break; 897 } 898 case BTRFS_SHARED_DATA_REF_KEY: { 899 /* SHARED DIRECT FULL backref */ 900 struct btrfs_delayed_data_ref *ref; 901 902 ref = btrfs_delayed_node_to_data_ref(node); 903 904 ret = add_direct_ref(fs_info, preftrees, 0, ref->parent, 905 node->bytenr, count, sc, 906 GFP_ATOMIC); 907 break; 908 } 909 default: 910 WARN_ON(1); 911 } 912 /* 913 * We must ignore BACKREF_FOUND_SHARED until all delayed 914 * refs have been checked. 915 */ 916 if (ret && (ret != BACKREF_FOUND_SHARED)) 917 break; 918 } 919 if (!ret) 920 ret = extent_is_shared(sc); 921 out: 922 spin_unlock(&head->lock); 923 return ret; 924 } 925 926 /* 927 * add all inline backrefs for bytenr to the list 928 * 929 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED. 930 */ 931 static int add_inline_refs(const struct btrfs_fs_info *fs_info, 932 struct btrfs_path *path, u64 bytenr, 933 int *info_level, struct preftrees *preftrees, 934 struct share_check *sc) 935 { 936 int ret = 0; 937 int slot; 938 struct extent_buffer *leaf; 939 struct btrfs_key key; 940 struct btrfs_key found_key; 941 unsigned long ptr; 942 unsigned long end; 943 struct btrfs_extent_item *ei; 944 u64 flags; 945 u64 item_size; 946 947 /* 948 * enumerate all inline refs 949 */ 950 leaf = path->nodes[0]; 951 slot = path->slots[0]; 952 953 item_size = btrfs_item_size(leaf, slot); 954 BUG_ON(item_size < sizeof(*ei)); 955 956 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); 957 flags = btrfs_extent_flags(leaf, ei); 958 btrfs_item_key_to_cpu(leaf, &found_key, slot); 959 960 ptr = (unsigned long)(ei + 1); 961 end = (unsigned long)ei + item_size; 962 963 if (found_key.type == BTRFS_EXTENT_ITEM_KEY && 964 flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { 965 struct btrfs_tree_block_info *info; 966 967 info = (struct btrfs_tree_block_info *)ptr; 968 *info_level = btrfs_tree_block_level(leaf, info); 969 ptr += sizeof(struct btrfs_tree_block_info); 970 BUG_ON(ptr > end); 971 } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) { 972 *info_level = found_key.offset; 973 } else { 974 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA)); 975 } 976 977 while (ptr < end) { 978 struct btrfs_extent_inline_ref *iref; 979 u64 offset; 980 int type; 981 982 iref = (struct btrfs_extent_inline_ref *)ptr; 983 type = btrfs_get_extent_inline_ref_type(leaf, iref, 984 BTRFS_REF_TYPE_ANY); 985 if (type == BTRFS_REF_TYPE_INVALID) 986 return -EUCLEAN; 987 988 offset = btrfs_extent_inline_ref_offset(leaf, iref); 989 990 switch (type) { 991 case BTRFS_SHARED_BLOCK_REF_KEY: 992 ret = add_direct_ref(fs_info, preftrees, 993 *info_level + 1, offset, 994 bytenr, 1, NULL, GFP_NOFS); 995 break; 996 case BTRFS_SHARED_DATA_REF_KEY: { 997 struct btrfs_shared_data_ref *sdref; 998 int count; 999 1000 sdref = (struct btrfs_shared_data_ref *)(iref + 1); 1001 count = btrfs_shared_data_ref_count(leaf, sdref); 1002 1003 ret = add_direct_ref(fs_info, preftrees, 0, offset, 1004 bytenr, count, sc, GFP_NOFS); 1005 break; 1006 } 1007 case BTRFS_TREE_BLOCK_REF_KEY: 1008 ret = add_indirect_ref(fs_info, preftrees, offset, 1009 NULL, *info_level + 1, 1010 bytenr, 1, NULL, GFP_NOFS); 1011 break; 1012 case BTRFS_EXTENT_DATA_REF_KEY: { 1013 struct btrfs_extent_data_ref *dref; 1014 int count; 1015 u64 root; 1016 1017 dref = (struct btrfs_extent_data_ref *)(&iref->offset); 1018 count = btrfs_extent_data_ref_count(leaf, dref); 1019 key.objectid = btrfs_extent_data_ref_objectid(leaf, 1020 dref); 1021 key.type = BTRFS_EXTENT_DATA_KEY; 1022 key.offset = btrfs_extent_data_ref_offset(leaf, dref); 1023 1024 if (sc && sc->inum && key.objectid != sc->inum) { 1025 ret = BACKREF_FOUND_SHARED; 1026 break; 1027 } 1028 1029 root = btrfs_extent_data_ref_root(leaf, dref); 1030 1031 ret = add_indirect_ref(fs_info, preftrees, root, 1032 &key, 0, bytenr, count, 1033 sc, GFP_NOFS); 1034 break; 1035 } 1036 default: 1037 WARN_ON(1); 1038 } 1039 if (ret) 1040 return ret; 1041 ptr += btrfs_extent_inline_ref_size(type); 1042 } 1043 1044 return 0; 1045 } 1046 1047 /* 1048 * add all non-inline backrefs for bytenr to the list 1049 * 1050 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED. 1051 */ 1052 static int add_keyed_refs(struct btrfs_root *extent_root, 1053 struct btrfs_path *path, u64 bytenr, 1054 int info_level, struct preftrees *preftrees, 1055 struct share_check *sc) 1056 { 1057 struct btrfs_fs_info *fs_info = extent_root->fs_info; 1058 int ret; 1059 int slot; 1060 struct extent_buffer *leaf; 1061 struct btrfs_key key; 1062 1063 while (1) { 1064 ret = btrfs_next_item(extent_root, path); 1065 if (ret < 0) 1066 break; 1067 if (ret) { 1068 ret = 0; 1069 break; 1070 } 1071 1072 slot = path->slots[0]; 1073 leaf = path->nodes[0]; 1074 btrfs_item_key_to_cpu(leaf, &key, slot); 1075 1076 if (key.objectid != bytenr) 1077 break; 1078 if (key.type < BTRFS_TREE_BLOCK_REF_KEY) 1079 continue; 1080 if (key.type > BTRFS_SHARED_DATA_REF_KEY) 1081 break; 1082 1083 switch (key.type) { 1084 case BTRFS_SHARED_BLOCK_REF_KEY: 1085 /* SHARED DIRECT METADATA backref */ 1086 ret = add_direct_ref(fs_info, preftrees, 1087 info_level + 1, key.offset, 1088 bytenr, 1, NULL, GFP_NOFS); 1089 break; 1090 case BTRFS_SHARED_DATA_REF_KEY: { 1091 /* SHARED DIRECT FULL backref */ 1092 struct btrfs_shared_data_ref *sdref; 1093 int count; 1094 1095 sdref = btrfs_item_ptr(leaf, slot, 1096 struct btrfs_shared_data_ref); 1097 count = btrfs_shared_data_ref_count(leaf, sdref); 1098 ret = add_direct_ref(fs_info, preftrees, 0, 1099 key.offset, bytenr, count, 1100 sc, GFP_NOFS); 1101 break; 1102 } 1103 case BTRFS_TREE_BLOCK_REF_KEY: 1104 /* NORMAL INDIRECT METADATA backref */ 1105 ret = add_indirect_ref(fs_info, preftrees, key.offset, 1106 NULL, info_level + 1, bytenr, 1107 1, NULL, GFP_NOFS); 1108 break; 1109 case BTRFS_EXTENT_DATA_REF_KEY: { 1110 /* NORMAL INDIRECT DATA backref */ 1111 struct btrfs_extent_data_ref *dref; 1112 int count; 1113 u64 root; 1114 1115 dref = btrfs_item_ptr(leaf, slot, 1116 struct btrfs_extent_data_ref); 1117 count = btrfs_extent_data_ref_count(leaf, dref); 1118 key.objectid = btrfs_extent_data_ref_objectid(leaf, 1119 dref); 1120 key.type = BTRFS_EXTENT_DATA_KEY; 1121 key.offset = btrfs_extent_data_ref_offset(leaf, dref); 1122 1123 if (sc && sc->inum && key.objectid != sc->inum) { 1124 ret = BACKREF_FOUND_SHARED; 1125 break; 1126 } 1127 1128 root = btrfs_extent_data_ref_root(leaf, dref); 1129 ret = add_indirect_ref(fs_info, preftrees, root, 1130 &key, 0, bytenr, count, 1131 sc, GFP_NOFS); 1132 break; 1133 } 1134 default: 1135 WARN_ON(1); 1136 } 1137 if (ret) 1138 return ret; 1139 1140 } 1141 1142 return ret; 1143 } 1144 1145 /* 1146 * this adds all existing backrefs (inline backrefs, backrefs and delayed 1147 * refs) for the given bytenr to the refs list, merges duplicates and resolves 1148 * indirect refs to their parent bytenr. 1149 * When roots are found, they're added to the roots list 1150 * 1151 * If time_seq is set to BTRFS_SEQ_LAST, it will not search delayed_refs, and 1152 * behave much like trans == NULL case, the difference only lies in it will not 1153 * commit root. 1154 * The special case is for qgroup to search roots in commit_transaction(). 1155 * 1156 * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a 1157 * shared extent is detected. 1158 * 1159 * Otherwise this returns 0 for success and <0 for an error. 1160 * 1161 * If ignore_offset is set to false, only extent refs whose offsets match 1162 * extent_item_pos are returned. If true, every extent ref is returned 1163 * and extent_item_pos is ignored. 1164 * 1165 * FIXME some caching might speed things up 1166 */ 1167 static int find_parent_nodes(struct btrfs_trans_handle *trans, 1168 struct btrfs_fs_info *fs_info, u64 bytenr, 1169 u64 time_seq, struct ulist *refs, 1170 struct ulist *roots, const u64 *extent_item_pos, 1171 struct share_check *sc, bool ignore_offset) 1172 { 1173 struct btrfs_root *root = fs_info->extent_root; 1174 struct btrfs_key key; 1175 struct btrfs_path *path; 1176 struct btrfs_delayed_ref_root *delayed_refs = NULL; 1177 struct btrfs_delayed_ref_head *head; 1178 int info_level = 0; 1179 int ret; 1180 struct prelim_ref *ref; 1181 struct rb_node *node; 1182 struct extent_inode_elem *eie = NULL; 1183 struct preftrees preftrees = { 1184 .direct = PREFTREE_INIT, 1185 .indirect = PREFTREE_INIT, 1186 .indirect_missing_keys = PREFTREE_INIT 1187 }; 1188 1189 key.objectid = bytenr; 1190 key.offset = (u64)-1; 1191 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA)) 1192 key.type = BTRFS_METADATA_ITEM_KEY; 1193 else 1194 key.type = BTRFS_EXTENT_ITEM_KEY; 1195 1196 path = btrfs_alloc_path(); 1197 if (!path) 1198 return -ENOMEM; 1199 if (!trans) { 1200 path->search_commit_root = 1; 1201 path->skip_locking = 1; 1202 } 1203 1204 if (time_seq == BTRFS_SEQ_LAST) 1205 path->skip_locking = 1; 1206 1207 /* 1208 * grab both a lock on the path and a lock on the delayed ref head. 1209 * We need both to get a consistent picture of how the refs look 1210 * at a specified point in time 1211 */ 1212 again: 1213 head = NULL; 1214 1215 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 1216 if (ret < 0) 1217 goto out; 1218 BUG_ON(ret == 0); 1219 1220 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS 1221 if (trans && likely(trans->type != __TRANS_DUMMY) && 1222 time_seq != BTRFS_SEQ_LAST) { 1223 #else 1224 if (trans && time_seq != BTRFS_SEQ_LAST) { 1225 #endif 1226 /* 1227 * look if there are updates for this ref queued and lock the 1228 * head 1229 */ 1230 delayed_refs = &trans->transaction->delayed_refs; 1231 spin_lock(&delayed_refs->lock); 1232 head = btrfs_find_delayed_ref_head(delayed_refs, bytenr); 1233 if (head) { 1234 if (!mutex_trylock(&head->mutex)) { 1235 refcount_inc(&head->refs); 1236 spin_unlock(&delayed_refs->lock); 1237 1238 btrfs_release_path(path); 1239 1240 /* 1241 * Mutex was contended, block until it's 1242 * released and try again 1243 */ 1244 mutex_lock(&head->mutex); 1245 mutex_unlock(&head->mutex); 1246 btrfs_put_delayed_ref_head(head); 1247 goto again; 1248 } 1249 spin_unlock(&delayed_refs->lock); 1250 ret = add_delayed_refs(fs_info, head, time_seq, 1251 &preftrees, sc); 1252 mutex_unlock(&head->mutex); 1253 if (ret) 1254 goto out; 1255 } else { 1256 spin_unlock(&delayed_refs->lock); 1257 } 1258 } 1259 1260 if (path->slots[0]) { 1261 struct extent_buffer *leaf; 1262 int slot; 1263 1264 path->slots[0]--; 1265 leaf = path->nodes[0]; 1266 slot = path->slots[0]; 1267 btrfs_item_key_to_cpu(leaf, &key, slot); 1268 if (key.objectid == bytenr && 1269 (key.type == BTRFS_EXTENT_ITEM_KEY || 1270 key.type == BTRFS_METADATA_ITEM_KEY)) { 1271 ret = add_inline_refs(fs_info, path, bytenr, 1272 &info_level, &preftrees, sc); 1273 if (ret) 1274 goto out; 1275 ret = add_keyed_refs(root, path, bytenr, info_level, 1276 &preftrees, sc); 1277 if (ret) 1278 goto out; 1279 } 1280 } 1281 1282 btrfs_release_path(path); 1283 1284 ret = add_missing_keys(fs_info, &preftrees, path->skip_locking == 0); 1285 if (ret) 1286 goto out; 1287 1288 WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root.rb_root)); 1289 1290 ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees, 1291 extent_item_pos, sc, ignore_offset); 1292 if (ret) 1293 goto out; 1294 1295 WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root.rb_root)); 1296 1297 /* 1298 * This walks the tree of merged and resolved refs. Tree blocks are 1299 * read in as needed. Unique entries are added to the ulist, and 1300 * the list of found roots is updated. 1301 * 1302 * We release the entire tree in one go before returning. 1303 */ 1304 node = rb_first_cached(&preftrees.direct.root); 1305 while (node) { 1306 ref = rb_entry(node, struct prelim_ref, rbnode); 1307 node = rb_next(&ref->rbnode); 1308 /* 1309 * ref->count < 0 can happen here if there are delayed 1310 * refs with a node->action of BTRFS_DROP_DELAYED_REF. 1311 * prelim_ref_insert() relies on this when merging 1312 * identical refs to keep the overall count correct. 1313 * prelim_ref_insert() will merge only those refs 1314 * which compare identically. Any refs having 1315 * e.g. different offsets would not be merged, 1316 * and would retain their original ref->count < 0. 1317 */ 1318 if (roots && ref->count && ref->root_id && ref->parent == 0) { 1319 if (sc && sc->root_objectid && 1320 ref->root_id != sc->root_objectid) { 1321 ret = BACKREF_FOUND_SHARED; 1322 goto out; 1323 } 1324 1325 /* no parent == root of tree */ 1326 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS); 1327 if (ret < 0) 1328 goto out; 1329 } 1330 if (ref->count && ref->parent) { 1331 if (extent_item_pos && !ref->inode_list && 1332 ref->level == 0) { 1333 struct extent_buffer *eb; 1334 1335 eb = read_tree_block(fs_info, ref->parent, 0, 1336 0, ref->level, NULL); 1337 if (IS_ERR(eb)) { 1338 ret = PTR_ERR(eb); 1339 goto out; 1340 } else if (!extent_buffer_uptodate(eb)) { 1341 free_extent_buffer(eb); 1342 ret = -EIO; 1343 goto out; 1344 } 1345 1346 if (!path->skip_locking) 1347 btrfs_tree_read_lock(eb); 1348 ret = find_extent_in_eb(eb, bytenr, 1349 *extent_item_pos, &eie, ignore_offset); 1350 if (!path->skip_locking) 1351 btrfs_tree_read_unlock(eb); 1352 free_extent_buffer(eb); 1353 if (ret < 0) 1354 goto out; 1355 ref->inode_list = eie; 1356 } 1357 ret = ulist_add_merge_ptr(refs, ref->parent, 1358 ref->inode_list, 1359 (void **)&eie, GFP_NOFS); 1360 if (ret < 0) 1361 goto out; 1362 if (!ret && extent_item_pos) { 1363 /* 1364 * we've recorded that parent, so we must extend 1365 * its inode list here 1366 */ 1367 BUG_ON(!eie); 1368 while (eie->next) 1369 eie = eie->next; 1370 eie->next = ref->inode_list; 1371 } 1372 eie = NULL; 1373 } 1374 cond_resched(); 1375 } 1376 1377 out: 1378 btrfs_free_path(path); 1379 1380 prelim_release(&preftrees.direct); 1381 prelim_release(&preftrees.indirect); 1382 prelim_release(&preftrees.indirect_missing_keys); 1383 1384 if (ret < 0) 1385 free_inode_elem_list(eie); 1386 return ret; 1387 } 1388 1389 static void free_leaf_list(struct ulist *blocks) 1390 { 1391 struct ulist_node *node = NULL; 1392 struct extent_inode_elem *eie; 1393 struct ulist_iterator uiter; 1394 1395 ULIST_ITER_INIT(&uiter); 1396 while ((node = ulist_next(blocks, &uiter))) { 1397 if (!node->aux) 1398 continue; 1399 eie = unode_aux_to_inode_list(node); 1400 free_inode_elem_list(eie); 1401 node->aux = 0; 1402 } 1403 1404 ulist_free(blocks); 1405 } 1406 1407 /* 1408 * Finds all leafs with a reference to the specified combination of bytenr and 1409 * offset. key_list_head will point to a list of corresponding keys (caller must 1410 * free each list element). The leafs will be stored in the leafs ulist, which 1411 * must be freed with ulist_free. 1412 * 1413 * returns 0 on success, <0 on error 1414 */ 1415 int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, 1416 struct btrfs_fs_info *fs_info, u64 bytenr, 1417 u64 time_seq, struct ulist **leafs, 1418 const u64 *extent_item_pos, bool ignore_offset) 1419 { 1420 int ret; 1421 1422 *leafs = ulist_alloc(GFP_NOFS); 1423 if (!*leafs) 1424 return -ENOMEM; 1425 1426 ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, 1427 *leafs, NULL, extent_item_pos, NULL, ignore_offset); 1428 if (ret < 0 && ret != -ENOENT) { 1429 free_leaf_list(*leafs); 1430 return ret; 1431 } 1432 1433 return 0; 1434 } 1435 1436 /* 1437 * walk all backrefs for a given extent to find all roots that reference this 1438 * extent. Walking a backref means finding all extents that reference this 1439 * extent and in turn walk the backrefs of those, too. Naturally this is a 1440 * recursive process, but here it is implemented in an iterative fashion: We 1441 * find all referencing extents for the extent in question and put them on a 1442 * list. In turn, we find all referencing extents for those, further appending 1443 * to the list. The way we iterate the list allows adding more elements after 1444 * the current while iterating. The process stops when we reach the end of the 1445 * list. Found roots are added to the roots list. 1446 * 1447 * returns 0 on success, < 0 on error. 1448 */ 1449 static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, 1450 struct btrfs_fs_info *fs_info, u64 bytenr, 1451 u64 time_seq, struct ulist **roots, 1452 bool ignore_offset) 1453 { 1454 struct ulist *tmp; 1455 struct ulist_node *node = NULL; 1456 struct ulist_iterator uiter; 1457 int ret; 1458 1459 tmp = ulist_alloc(GFP_NOFS); 1460 if (!tmp) 1461 return -ENOMEM; 1462 *roots = ulist_alloc(GFP_NOFS); 1463 if (!*roots) { 1464 ulist_free(tmp); 1465 return -ENOMEM; 1466 } 1467 1468 ULIST_ITER_INIT(&uiter); 1469 while (1) { 1470 ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, 1471 tmp, *roots, NULL, NULL, ignore_offset); 1472 if (ret < 0 && ret != -ENOENT) { 1473 ulist_free(tmp); 1474 ulist_free(*roots); 1475 *roots = NULL; 1476 return ret; 1477 } 1478 node = ulist_next(tmp, &uiter); 1479 if (!node) 1480 break; 1481 bytenr = node->val; 1482 cond_resched(); 1483 } 1484 1485 ulist_free(tmp); 1486 return 0; 1487 } 1488 1489 int btrfs_find_all_roots(struct btrfs_trans_handle *trans, 1490 struct btrfs_fs_info *fs_info, u64 bytenr, 1491 u64 time_seq, struct ulist **roots, 1492 bool skip_commit_root_sem) 1493 { 1494 int ret; 1495 1496 if (!trans && !skip_commit_root_sem) 1497 down_read(&fs_info->commit_root_sem); 1498 ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr, 1499 time_seq, roots, false); 1500 if (!trans && !skip_commit_root_sem) 1501 up_read(&fs_info->commit_root_sem); 1502 return ret; 1503 } 1504 1505 /** 1506 * Check if an extent is shared or not 1507 * 1508 * @root: root inode belongs to 1509 * @inum: inode number of the inode whose extent we are checking 1510 * @bytenr: logical bytenr of the extent we are checking 1511 * @roots: list of roots this extent is shared among 1512 * @tmp: temporary list used for iteration 1513 * 1514 * btrfs_check_shared uses the backref walking code but will short 1515 * circuit as soon as it finds a root or inode that doesn't match the 1516 * one passed in. This provides a significant performance benefit for 1517 * callers (such as fiemap) which want to know whether the extent is 1518 * shared but do not need a ref count. 1519 * 1520 * This attempts to attach to the running transaction in order to account for 1521 * delayed refs, but continues on even when no running transaction exists. 1522 * 1523 * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error. 1524 */ 1525 int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr, 1526 struct ulist *roots, struct ulist *tmp) 1527 { 1528 struct btrfs_fs_info *fs_info = root->fs_info; 1529 struct btrfs_trans_handle *trans; 1530 struct ulist_iterator uiter; 1531 struct ulist_node *node; 1532 struct btrfs_seq_list elem = BTRFS_SEQ_LIST_INIT(elem); 1533 int ret = 0; 1534 struct share_check shared = { 1535 .root_objectid = root->root_key.objectid, 1536 .inum = inum, 1537 .share_count = 0, 1538 }; 1539 1540 ulist_init(roots); 1541 ulist_init(tmp); 1542 1543 trans = btrfs_join_transaction_nostart(root); 1544 if (IS_ERR(trans)) { 1545 if (PTR_ERR(trans) != -ENOENT && PTR_ERR(trans) != -EROFS) { 1546 ret = PTR_ERR(trans); 1547 goto out; 1548 } 1549 trans = NULL; 1550 down_read(&fs_info->commit_root_sem); 1551 } else { 1552 btrfs_get_tree_mod_seq(fs_info, &elem); 1553 } 1554 1555 ULIST_ITER_INIT(&uiter); 1556 while (1) { 1557 ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp, 1558 roots, NULL, &shared, false); 1559 if (ret == BACKREF_FOUND_SHARED) { 1560 /* this is the only condition under which we return 1 */ 1561 ret = 1; 1562 break; 1563 } 1564 if (ret < 0 && ret != -ENOENT) 1565 break; 1566 ret = 0; 1567 node = ulist_next(tmp, &uiter); 1568 if (!node) 1569 break; 1570 bytenr = node->val; 1571 shared.share_count = 0; 1572 cond_resched(); 1573 } 1574 1575 if (trans) { 1576 btrfs_put_tree_mod_seq(fs_info, &elem); 1577 btrfs_end_transaction(trans); 1578 } else { 1579 up_read(&fs_info->commit_root_sem); 1580 } 1581 out: 1582 ulist_release(roots); 1583 ulist_release(tmp); 1584 return ret; 1585 } 1586 1587 int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid, 1588 u64 start_off, struct btrfs_path *path, 1589 struct btrfs_inode_extref **ret_extref, 1590 u64 *found_off) 1591 { 1592 int ret, slot; 1593 struct btrfs_key key; 1594 struct btrfs_key found_key; 1595 struct btrfs_inode_extref *extref; 1596 const struct extent_buffer *leaf; 1597 unsigned long ptr; 1598 1599 key.objectid = inode_objectid; 1600 key.type = BTRFS_INODE_EXTREF_KEY; 1601 key.offset = start_off; 1602 1603 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 1604 if (ret < 0) 1605 return ret; 1606 1607 while (1) { 1608 leaf = path->nodes[0]; 1609 slot = path->slots[0]; 1610 if (slot >= btrfs_header_nritems(leaf)) { 1611 /* 1612 * If the item at offset is not found, 1613 * btrfs_search_slot will point us to the slot 1614 * where it should be inserted. In our case 1615 * that will be the slot directly before the 1616 * next INODE_REF_KEY_V2 item. In the case 1617 * that we're pointing to the last slot in a 1618 * leaf, we must move one leaf over. 1619 */ 1620 ret = btrfs_next_leaf(root, path); 1621 if (ret) { 1622 if (ret >= 1) 1623 ret = -ENOENT; 1624 break; 1625 } 1626 continue; 1627 } 1628 1629 btrfs_item_key_to_cpu(leaf, &found_key, slot); 1630 1631 /* 1632 * Check that we're still looking at an extended ref key for 1633 * this particular objectid. If we have different 1634 * objectid or type then there are no more to be found 1635 * in the tree and we can exit. 1636 */ 1637 ret = -ENOENT; 1638 if (found_key.objectid != inode_objectid) 1639 break; 1640 if (found_key.type != BTRFS_INODE_EXTREF_KEY) 1641 break; 1642 1643 ret = 0; 1644 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 1645 extref = (struct btrfs_inode_extref *)ptr; 1646 *ret_extref = extref; 1647 if (found_off) 1648 *found_off = found_key.offset; 1649 break; 1650 } 1651 1652 return ret; 1653 } 1654 1655 /* 1656 * this iterates to turn a name (from iref/extref) into a full filesystem path. 1657 * Elements of the path are separated by '/' and the path is guaranteed to be 1658 * 0-terminated. the path is only given within the current file system. 1659 * Therefore, it never starts with a '/'. the caller is responsible to provide 1660 * "size" bytes in "dest". the dest buffer will be filled backwards. finally, 1661 * the start point of the resulting string is returned. this pointer is within 1662 * dest, normally. 1663 * in case the path buffer would overflow, the pointer is decremented further 1664 * as if output was written to the buffer, though no more output is actually 1665 * generated. that way, the caller can determine how much space would be 1666 * required for the path to fit into the buffer. in that case, the returned 1667 * value will be smaller than dest. callers must check this! 1668 */ 1669 char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path, 1670 u32 name_len, unsigned long name_off, 1671 struct extent_buffer *eb_in, u64 parent, 1672 char *dest, u32 size) 1673 { 1674 int slot; 1675 u64 next_inum; 1676 int ret; 1677 s64 bytes_left = ((s64)size) - 1; 1678 struct extent_buffer *eb = eb_in; 1679 struct btrfs_key found_key; 1680 struct btrfs_inode_ref *iref; 1681 1682 if (bytes_left >= 0) 1683 dest[bytes_left] = '\0'; 1684 1685 while (1) { 1686 bytes_left -= name_len; 1687 if (bytes_left >= 0) 1688 read_extent_buffer(eb, dest + bytes_left, 1689 name_off, name_len); 1690 if (eb != eb_in) { 1691 if (!path->skip_locking) 1692 btrfs_tree_read_unlock(eb); 1693 free_extent_buffer(eb); 1694 } 1695 ret = btrfs_find_item(fs_root, path, parent, 0, 1696 BTRFS_INODE_REF_KEY, &found_key); 1697 if (ret > 0) 1698 ret = -ENOENT; 1699 if (ret) 1700 break; 1701 1702 next_inum = found_key.offset; 1703 1704 /* regular exit ahead */ 1705 if (parent == next_inum) 1706 break; 1707 1708 slot = path->slots[0]; 1709 eb = path->nodes[0]; 1710 /* make sure we can use eb after releasing the path */ 1711 if (eb != eb_in) { 1712 path->nodes[0] = NULL; 1713 path->locks[0] = 0; 1714 } 1715 btrfs_release_path(path); 1716 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref); 1717 1718 name_len = btrfs_inode_ref_name_len(eb, iref); 1719 name_off = (unsigned long)(iref + 1); 1720 1721 parent = next_inum; 1722 --bytes_left; 1723 if (bytes_left >= 0) 1724 dest[bytes_left] = '/'; 1725 } 1726 1727 btrfs_release_path(path); 1728 1729 if (ret) 1730 return ERR_PTR(ret); 1731 1732 return dest + bytes_left; 1733 } 1734 1735 /* 1736 * this makes the path point to (logical EXTENT_ITEM *) 1737 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for 1738 * tree blocks and <0 on error. 1739 */ 1740 int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, 1741 struct btrfs_path *path, struct btrfs_key *found_key, 1742 u64 *flags_ret) 1743 { 1744 int ret; 1745 u64 flags; 1746 u64 size = 0; 1747 u32 item_size; 1748 const struct extent_buffer *eb; 1749 struct btrfs_extent_item *ei; 1750 struct btrfs_key key; 1751 1752 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA)) 1753 key.type = BTRFS_METADATA_ITEM_KEY; 1754 else 1755 key.type = BTRFS_EXTENT_ITEM_KEY; 1756 key.objectid = logical; 1757 key.offset = (u64)-1; 1758 1759 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0); 1760 if (ret < 0) 1761 return ret; 1762 1763 ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0); 1764 if (ret) { 1765 if (ret > 0) 1766 ret = -ENOENT; 1767 return ret; 1768 } 1769 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]); 1770 if (found_key->type == BTRFS_METADATA_ITEM_KEY) 1771 size = fs_info->nodesize; 1772 else if (found_key->type == BTRFS_EXTENT_ITEM_KEY) 1773 size = found_key->offset; 1774 1775 if (found_key->objectid > logical || 1776 found_key->objectid + size <= logical) { 1777 btrfs_debug(fs_info, 1778 "logical %llu is not within any extent", logical); 1779 return -ENOENT; 1780 } 1781 1782 eb = path->nodes[0]; 1783 item_size = btrfs_item_size(eb, path->slots[0]); 1784 BUG_ON(item_size < sizeof(*ei)); 1785 1786 ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item); 1787 flags = btrfs_extent_flags(eb, ei); 1788 1789 btrfs_debug(fs_info, 1790 "logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u", 1791 logical, logical - found_key->objectid, found_key->objectid, 1792 found_key->offset, flags, item_size); 1793 1794 WARN_ON(!flags_ret); 1795 if (flags_ret) { 1796 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) 1797 *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK; 1798 else if (flags & BTRFS_EXTENT_FLAG_DATA) 1799 *flags_ret = BTRFS_EXTENT_FLAG_DATA; 1800 else 1801 BUG(); 1802 return 0; 1803 } 1804 1805 return -EIO; 1806 } 1807 1808 /* 1809 * helper function to iterate extent inline refs. ptr must point to a 0 value 1810 * for the first call and may be modified. it is used to track state. 1811 * if more refs exist, 0 is returned and the next call to 1812 * get_extent_inline_ref must pass the modified ptr parameter to get the 1813 * next ref. after the last ref was processed, 1 is returned. 1814 * returns <0 on error 1815 */ 1816 static int get_extent_inline_ref(unsigned long *ptr, 1817 const struct extent_buffer *eb, 1818 const struct btrfs_key *key, 1819 const struct btrfs_extent_item *ei, 1820 u32 item_size, 1821 struct btrfs_extent_inline_ref **out_eiref, 1822 int *out_type) 1823 { 1824 unsigned long end; 1825 u64 flags; 1826 struct btrfs_tree_block_info *info; 1827 1828 if (!*ptr) { 1829 /* first call */ 1830 flags = btrfs_extent_flags(eb, ei); 1831 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { 1832 if (key->type == BTRFS_METADATA_ITEM_KEY) { 1833 /* a skinny metadata extent */ 1834 *out_eiref = 1835 (struct btrfs_extent_inline_ref *)(ei + 1); 1836 } else { 1837 WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY); 1838 info = (struct btrfs_tree_block_info *)(ei + 1); 1839 *out_eiref = 1840 (struct btrfs_extent_inline_ref *)(info + 1); 1841 } 1842 } else { 1843 *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1); 1844 } 1845 *ptr = (unsigned long)*out_eiref; 1846 if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size) 1847 return -ENOENT; 1848 } 1849 1850 end = (unsigned long)ei + item_size; 1851 *out_eiref = (struct btrfs_extent_inline_ref *)(*ptr); 1852 *out_type = btrfs_get_extent_inline_ref_type(eb, *out_eiref, 1853 BTRFS_REF_TYPE_ANY); 1854 if (*out_type == BTRFS_REF_TYPE_INVALID) 1855 return -EUCLEAN; 1856 1857 *ptr += btrfs_extent_inline_ref_size(*out_type); 1858 WARN_ON(*ptr > end); 1859 if (*ptr == end) 1860 return 1; /* last */ 1861 1862 return 0; 1863 } 1864 1865 /* 1866 * reads the tree block backref for an extent. tree level and root are returned 1867 * through out_level and out_root. ptr must point to a 0 value for the first 1868 * call and may be modified (see get_extent_inline_ref comment). 1869 * returns 0 if data was provided, 1 if there was no more data to provide or 1870 * <0 on error. 1871 */ 1872 int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb, 1873 struct btrfs_key *key, struct btrfs_extent_item *ei, 1874 u32 item_size, u64 *out_root, u8 *out_level) 1875 { 1876 int ret; 1877 int type; 1878 struct btrfs_extent_inline_ref *eiref; 1879 1880 if (*ptr == (unsigned long)-1) 1881 return 1; 1882 1883 while (1) { 1884 ret = get_extent_inline_ref(ptr, eb, key, ei, item_size, 1885 &eiref, &type); 1886 if (ret < 0) 1887 return ret; 1888 1889 if (type == BTRFS_TREE_BLOCK_REF_KEY || 1890 type == BTRFS_SHARED_BLOCK_REF_KEY) 1891 break; 1892 1893 if (ret == 1) 1894 return 1; 1895 } 1896 1897 /* we can treat both ref types equally here */ 1898 *out_root = btrfs_extent_inline_ref_offset(eb, eiref); 1899 1900 if (key->type == BTRFS_EXTENT_ITEM_KEY) { 1901 struct btrfs_tree_block_info *info; 1902 1903 info = (struct btrfs_tree_block_info *)(ei + 1); 1904 *out_level = btrfs_tree_block_level(eb, info); 1905 } else { 1906 ASSERT(key->type == BTRFS_METADATA_ITEM_KEY); 1907 *out_level = (u8)key->offset; 1908 } 1909 1910 if (ret == 1) 1911 *ptr = (unsigned long)-1; 1912 1913 return 0; 1914 } 1915 1916 static int iterate_leaf_refs(struct btrfs_fs_info *fs_info, 1917 struct extent_inode_elem *inode_list, 1918 u64 root, u64 extent_item_objectid, 1919 iterate_extent_inodes_t *iterate, void *ctx) 1920 { 1921 struct extent_inode_elem *eie; 1922 int ret = 0; 1923 1924 for (eie = inode_list; eie; eie = eie->next) { 1925 btrfs_debug(fs_info, 1926 "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu", 1927 extent_item_objectid, eie->inum, 1928 eie->offset, root); 1929 ret = iterate(eie->inum, eie->offset, root, ctx); 1930 if (ret) { 1931 btrfs_debug(fs_info, 1932 "stopping iteration for %llu due to ret=%d", 1933 extent_item_objectid, ret); 1934 break; 1935 } 1936 } 1937 1938 return ret; 1939 } 1940 1941 /* 1942 * calls iterate() for every inode that references the extent identified by 1943 * the given parameters. 1944 * when the iterator function returns a non-zero value, iteration stops. 1945 */ 1946 int iterate_extent_inodes(struct btrfs_fs_info *fs_info, 1947 u64 extent_item_objectid, u64 extent_item_pos, 1948 int search_commit_root, 1949 iterate_extent_inodes_t *iterate, void *ctx, 1950 bool ignore_offset) 1951 { 1952 int ret; 1953 struct btrfs_trans_handle *trans = NULL; 1954 struct ulist *refs = NULL; 1955 struct ulist *roots = NULL; 1956 struct ulist_node *ref_node = NULL; 1957 struct ulist_node *root_node = NULL; 1958 struct btrfs_seq_list seq_elem = BTRFS_SEQ_LIST_INIT(seq_elem); 1959 struct ulist_iterator ref_uiter; 1960 struct ulist_iterator root_uiter; 1961 1962 btrfs_debug(fs_info, "resolving all inodes for extent %llu", 1963 extent_item_objectid); 1964 1965 if (!search_commit_root) { 1966 trans = btrfs_attach_transaction(fs_info->extent_root); 1967 if (IS_ERR(trans)) { 1968 if (PTR_ERR(trans) != -ENOENT && 1969 PTR_ERR(trans) != -EROFS) 1970 return PTR_ERR(trans); 1971 trans = NULL; 1972 } 1973 } 1974 1975 if (trans) 1976 btrfs_get_tree_mod_seq(fs_info, &seq_elem); 1977 else 1978 down_read(&fs_info->commit_root_sem); 1979 1980 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid, 1981 seq_elem.seq, &refs, 1982 &extent_item_pos, ignore_offset); 1983 if (ret) 1984 goto out; 1985 1986 ULIST_ITER_INIT(&ref_uiter); 1987 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) { 1988 ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val, 1989 seq_elem.seq, &roots, 1990 ignore_offset); 1991 if (ret) 1992 break; 1993 ULIST_ITER_INIT(&root_uiter); 1994 while (!ret && (root_node = ulist_next(roots, &root_uiter))) { 1995 btrfs_debug(fs_info, 1996 "root %llu references leaf %llu, data list %#llx", 1997 root_node->val, ref_node->val, 1998 ref_node->aux); 1999 ret = iterate_leaf_refs(fs_info, 2000 (struct extent_inode_elem *) 2001 (uintptr_t)ref_node->aux, 2002 root_node->val, 2003 extent_item_objectid, 2004 iterate, ctx); 2005 } 2006 ulist_free(roots); 2007 } 2008 2009 free_leaf_list(refs); 2010 out: 2011 if (trans) { 2012 btrfs_put_tree_mod_seq(fs_info, &seq_elem); 2013 btrfs_end_transaction(trans); 2014 } else { 2015 up_read(&fs_info->commit_root_sem); 2016 } 2017 2018 return ret; 2019 } 2020 2021 int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, 2022 struct btrfs_path *path, 2023 iterate_extent_inodes_t *iterate, void *ctx, 2024 bool ignore_offset) 2025 { 2026 int ret; 2027 u64 extent_item_pos; 2028 u64 flags = 0; 2029 struct btrfs_key found_key; 2030 int search_commit_root = path->search_commit_root; 2031 2032 ret = extent_from_logical(fs_info, logical, path, &found_key, &flags); 2033 btrfs_release_path(path); 2034 if (ret < 0) 2035 return ret; 2036 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) 2037 return -EINVAL; 2038 2039 extent_item_pos = logical - found_key.objectid; 2040 ret = iterate_extent_inodes(fs_info, found_key.objectid, 2041 extent_item_pos, search_commit_root, 2042 iterate, ctx, ignore_offset); 2043 2044 return ret; 2045 } 2046 2047 typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off, 2048 struct extent_buffer *eb, void *ctx); 2049 2050 static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root, 2051 struct btrfs_path *path, 2052 iterate_irefs_t *iterate, void *ctx) 2053 { 2054 int ret = 0; 2055 int slot; 2056 u32 cur; 2057 u32 len; 2058 u32 name_len; 2059 u64 parent = 0; 2060 int found = 0; 2061 struct extent_buffer *eb; 2062 struct btrfs_inode_ref *iref; 2063 struct btrfs_key found_key; 2064 2065 while (!ret) { 2066 ret = btrfs_find_item(fs_root, path, inum, 2067 parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY, 2068 &found_key); 2069 2070 if (ret < 0) 2071 break; 2072 if (ret) { 2073 ret = found ? 0 : -ENOENT; 2074 break; 2075 } 2076 ++found; 2077 2078 parent = found_key.offset; 2079 slot = path->slots[0]; 2080 eb = btrfs_clone_extent_buffer(path->nodes[0]); 2081 if (!eb) { 2082 ret = -ENOMEM; 2083 break; 2084 } 2085 btrfs_release_path(path); 2086 2087 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref); 2088 2089 for (cur = 0; cur < btrfs_item_size(eb, slot); cur += len) { 2090 name_len = btrfs_inode_ref_name_len(eb, iref); 2091 /* path must be released before calling iterate()! */ 2092 btrfs_debug(fs_root->fs_info, 2093 "following ref at offset %u for inode %llu in tree %llu", 2094 cur, found_key.objectid, 2095 fs_root->root_key.objectid); 2096 ret = iterate(parent, name_len, 2097 (unsigned long)(iref + 1), eb, ctx); 2098 if (ret) 2099 break; 2100 len = sizeof(*iref) + name_len; 2101 iref = (struct btrfs_inode_ref *)((char *)iref + len); 2102 } 2103 free_extent_buffer(eb); 2104 } 2105 2106 btrfs_release_path(path); 2107 2108 return ret; 2109 } 2110 2111 static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root, 2112 struct btrfs_path *path, 2113 iterate_irefs_t *iterate, void *ctx) 2114 { 2115 int ret; 2116 int slot; 2117 u64 offset = 0; 2118 u64 parent; 2119 int found = 0; 2120 struct extent_buffer *eb; 2121 struct btrfs_inode_extref *extref; 2122 u32 item_size; 2123 u32 cur_offset; 2124 unsigned long ptr; 2125 2126 while (1) { 2127 ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref, 2128 &offset); 2129 if (ret < 0) 2130 break; 2131 if (ret) { 2132 ret = found ? 0 : -ENOENT; 2133 break; 2134 } 2135 ++found; 2136 2137 slot = path->slots[0]; 2138 eb = btrfs_clone_extent_buffer(path->nodes[0]); 2139 if (!eb) { 2140 ret = -ENOMEM; 2141 break; 2142 } 2143 btrfs_release_path(path); 2144 2145 item_size = btrfs_item_size(eb, slot); 2146 ptr = btrfs_item_ptr_offset(eb, slot); 2147 cur_offset = 0; 2148 2149 while (cur_offset < item_size) { 2150 u32 name_len; 2151 2152 extref = (struct btrfs_inode_extref *)(ptr + cur_offset); 2153 parent = btrfs_inode_extref_parent(eb, extref); 2154 name_len = btrfs_inode_extref_name_len(eb, extref); 2155 ret = iterate(parent, name_len, 2156 (unsigned long)&extref->name, eb, ctx); 2157 if (ret) 2158 break; 2159 2160 cur_offset += btrfs_inode_extref_name_len(eb, extref); 2161 cur_offset += sizeof(*extref); 2162 } 2163 free_extent_buffer(eb); 2164 2165 offset++; 2166 } 2167 2168 btrfs_release_path(path); 2169 2170 return ret; 2171 } 2172 2173 static int iterate_irefs(u64 inum, struct btrfs_root *fs_root, 2174 struct btrfs_path *path, iterate_irefs_t *iterate, 2175 void *ctx) 2176 { 2177 int ret; 2178 int found_refs = 0; 2179 2180 ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx); 2181 if (!ret) 2182 ++found_refs; 2183 else if (ret != -ENOENT) 2184 return ret; 2185 2186 ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx); 2187 if (ret == -ENOENT && found_refs) 2188 return 0; 2189 2190 return ret; 2191 } 2192 2193 /* 2194 * returns 0 if the path could be dumped (probably truncated) 2195 * returns <0 in case of an error 2196 */ 2197 static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off, 2198 struct extent_buffer *eb, void *ctx) 2199 { 2200 struct inode_fs_paths *ipath = ctx; 2201 char *fspath; 2202 char *fspath_min; 2203 int i = ipath->fspath->elem_cnt; 2204 const int s_ptr = sizeof(char *); 2205 u32 bytes_left; 2206 2207 bytes_left = ipath->fspath->bytes_left > s_ptr ? 2208 ipath->fspath->bytes_left - s_ptr : 0; 2209 2210 fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr; 2211 fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len, 2212 name_off, eb, inum, fspath_min, bytes_left); 2213 if (IS_ERR(fspath)) 2214 return PTR_ERR(fspath); 2215 2216 if (fspath > fspath_min) { 2217 ipath->fspath->val[i] = (u64)(unsigned long)fspath; 2218 ++ipath->fspath->elem_cnt; 2219 ipath->fspath->bytes_left = fspath - fspath_min; 2220 } else { 2221 ++ipath->fspath->elem_missed; 2222 ipath->fspath->bytes_missing += fspath_min - fspath; 2223 ipath->fspath->bytes_left = 0; 2224 } 2225 2226 return 0; 2227 } 2228 2229 /* 2230 * this dumps all file system paths to the inode into the ipath struct, provided 2231 * is has been created large enough. each path is zero-terminated and accessed 2232 * from ipath->fspath->val[i]. 2233 * when it returns, there are ipath->fspath->elem_cnt number of paths available 2234 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the 2235 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise, 2236 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would 2237 * have been needed to return all paths. 2238 */ 2239 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath) 2240 { 2241 return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path, 2242 inode_to_path, ipath); 2243 } 2244 2245 struct btrfs_data_container *init_data_container(u32 total_bytes) 2246 { 2247 struct btrfs_data_container *data; 2248 size_t alloc_bytes; 2249 2250 alloc_bytes = max_t(size_t, total_bytes, sizeof(*data)); 2251 data = kvmalloc(alloc_bytes, GFP_KERNEL); 2252 if (!data) 2253 return ERR_PTR(-ENOMEM); 2254 2255 if (total_bytes >= sizeof(*data)) { 2256 data->bytes_left = total_bytes - sizeof(*data); 2257 data->bytes_missing = 0; 2258 } else { 2259 data->bytes_missing = sizeof(*data) - total_bytes; 2260 data->bytes_left = 0; 2261 } 2262 2263 data->elem_cnt = 0; 2264 data->elem_missed = 0; 2265 2266 return data; 2267 } 2268 2269 /* 2270 * allocates space to return multiple file system paths for an inode. 2271 * total_bytes to allocate are passed, note that space usable for actual path 2272 * information will be total_bytes - sizeof(struct inode_fs_paths). 2273 * the returned pointer must be freed with free_ipath() in the end. 2274 */ 2275 struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root, 2276 struct btrfs_path *path) 2277 { 2278 struct inode_fs_paths *ifp; 2279 struct btrfs_data_container *fspath; 2280 2281 fspath = init_data_container(total_bytes); 2282 if (IS_ERR(fspath)) 2283 return ERR_CAST(fspath); 2284 2285 ifp = kmalloc(sizeof(*ifp), GFP_KERNEL); 2286 if (!ifp) { 2287 kvfree(fspath); 2288 return ERR_PTR(-ENOMEM); 2289 } 2290 2291 ifp->btrfs_path = path; 2292 ifp->fspath = fspath; 2293 ifp->fs_root = fs_root; 2294 2295 return ifp; 2296 } 2297 2298 void free_ipath(struct inode_fs_paths *ipath) 2299 { 2300 if (!ipath) 2301 return; 2302 kvfree(ipath->fspath); 2303 kfree(ipath); 2304 } 2305 2306 struct btrfs_backref_iter *btrfs_backref_iter_alloc( 2307 struct btrfs_fs_info *fs_info, gfp_t gfp_flag) 2308 { 2309 struct btrfs_backref_iter *ret; 2310 2311 ret = kzalloc(sizeof(*ret), gfp_flag); 2312 if (!ret) 2313 return NULL; 2314 2315 ret->path = btrfs_alloc_path(); 2316 if (!ret->path) { 2317 kfree(ret); 2318 return NULL; 2319 } 2320 2321 /* Current backref iterator only supports iteration in commit root */ 2322 ret->path->search_commit_root = 1; 2323 ret->path->skip_locking = 1; 2324 ret->fs_info = fs_info; 2325 2326 return ret; 2327 } 2328 2329 int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr) 2330 { 2331 struct btrfs_fs_info *fs_info = iter->fs_info; 2332 struct btrfs_path *path = iter->path; 2333 struct btrfs_extent_item *ei; 2334 struct btrfs_key key; 2335 int ret; 2336 2337 key.objectid = bytenr; 2338 key.type = BTRFS_METADATA_ITEM_KEY; 2339 key.offset = (u64)-1; 2340 iter->bytenr = bytenr; 2341 2342 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0); 2343 if (ret < 0) 2344 return ret; 2345 if (ret == 0) { 2346 ret = -EUCLEAN; 2347 goto release; 2348 } 2349 if (path->slots[0] == 0) { 2350 WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG)); 2351 ret = -EUCLEAN; 2352 goto release; 2353 } 2354 path->slots[0]--; 2355 2356 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 2357 if ((key.type != BTRFS_EXTENT_ITEM_KEY && 2358 key.type != BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) { 2359 ret = -ENOENT; 2360 goto release; 2361 } 2362 memcpy(&iter->cur_key, &key, sizeof(key)); 2363 iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0], 2364 path->slots[0]); 2365 iter->end_ptr = (u32)(iter->item_ptr + 2366 btrfs_item_size(path->nodes[0], path->slots[0])); 2367 ei = btrfs_item_ptr(path->nodes[0], path->slots[0], 2368 struct btrfs_extent_item); 2369 2370 /* 2371 * Only support iteration on tree backref yet. 2372 * 2373 * This is an extra precaution for non skinny-metadata, where 2374 * EXTENT_ITEM is also used for tree blocks, that we can only use 2375 * extent flags to determine if it's a tree block. 2376 */ 2377 if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) { 2378 ret = -ENOTSUPP; 2379 goto release; 2380 } 2381 iter->cur_ptr = (u32)(iter->item_ptr + sizeof(*ei)); 2382 2383 /* If there is no inline backref, go search for keyed backref */ 2384 if (iter->cur_ptr >= iter->end_ptr) { 2385 ret = btrfs_next_item(fs_info->extent_root, path); 2386 2387 /* No inline nor keyed ref */ 2388 if (ret > 0) { 2389 ret = -ENOENT; 2390 goto release; 2391 } 2392 if (ret < 0) 2393 goto release; 2394 2395 btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key, 2396 path->slots[0]); 2397 if (iter->cur_key.objectid != bytenr || 2398 (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY && 2399 iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) { 2400 ret = -ENOENT; 2401 goto release; 2402 } 2403 iter->cur_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0], 2404 path->slots[0]); 2405 iter->item_ptr = iter->cur_ptr; 2406 iter->end_ptr = (u32)(iter->item_ptr + btrfs_item_size( 2407 path->nodes[0], path->slots[0])); 2408 } 2409 2410 return 0; 2411 release: 2412 btrfs_backref_iter_release(iter); 2413 return ret; 2414 } 2415 2416 /* 2417 * Go to the next backref item of current bytenr, can be either inlined or 2418 * keyed. 2419 * 2420 * Caller needs to check whether it's inline ref or not by iter->cur_key. 2421 * 2422 * Return 0 if we get next backref without problem. 2423 * Return >0 if there is no extra backref for this bytenr. 2424 * Return <0 if there is something wrong happened. 2425 */ 2426 int btrfs_backref_iter_next(struct btrfs_backref_iter *iter) 2427 { 2428 struct extent_buffer *eb = btrfs_backref_get_eb(iter); 2429 struct btrfs_path *path = iter->path; 2430 struct btrfs_extent_inline_ref *iref; 2431 int ret; 2432 u32 size; 2433 2434 if (btrfs_backref_iter_is_inline_ref(iter)) { 2435 /* We're still inside the inline refs */ 2436 ASSERT(iter->cur_ptr < iter->end_ptr); 2437 2438 if (btrfs_backref_has_tree_block_info(iter)) { 2439 /* First tree block info */ 2440 size = sizeof(struct btrfs_tree_block_info); 2441 } else { 2442 /* Use inline ref type to determine the size */ 2443 int type; 2444 2445 iref = (struct btrfs_extent_inline_ref *) 2446 ((unsigned long)iter->cur_ptr); 2447 type = btrfs_extent_inline_ref_type(eb, iref); 2448 2449 size = btrfs_extent_inline_ref_size(type); 2450 } 2451 iter->cur_ptr += size; 2452 if (iter->cur_ptr < iter->end_ptr) 2453 return 0; 2454 2455 /* All inline items iterated, fall through */ 2456 } 2457 2458 /* We're at keyed items, there is no inline item, go to the next one */ 2459 ret = btrfs_next_item(iter->fs_info->extent_root, iter->path); 2460 if (ret) 2461 return ret; 2462 2463 btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key, path->slots[0]); 2464 if (iter->cur_key.objectid != iter->bytenr || 2465 (iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY && 2466 iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY)) 2467 return 1; 2468 iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0], 2469 path->slots[0]); 2470 iter->cur_ptr = iter->item_ptr; 2471 iter->end_ptr = iter->item_ptr + (u32)btrfs_item_size(path->nodes[0], 2472 path->slots[0]); 2473 return 0; 2474 } 2475 2476 void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info, 2477 struct btrfs_backref_cache *cache, int is_reloc) 2478 { 2479 int i; 2480 2481 cache->rb_root = RB_ROOT; 2482 for (i = 0; i < BTRFS_MAX_LEVEL; i++) 2483 INIT_LIST_HEAD(&cache->pending[i]); 2484 INIT_LIST_HEAD(&cache->changed); 2485 INIT_LIST_HEAD(&cache->detached); 2486 INIT_LIST_HEAD(&cache->leaves); 2487 INIT_LIST_HEAD(&cache->pending_edge); 2488 INIT_LIST_HEAD(&cache->useless_node); 2489 cache->fs_info = fs_info; 2490 cache->is_reloc = is_reloc; 2491 } 2492 2493 struct btrfs_backref_node *btrfs_backref_alloc_node( 2494 struct btrfs_backref_cache *cache, u64 bytenr, int level) 2495 { 2496 struct btrfs_backref_node *node; 2497 2498 ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL); 2499 node = kzalloc(sizeof(*node), GFP_NOFS); 2500 if (!node) 2501 return node; 2502 2503 INIT_LIST_HEAD(&node->list); 2504 INIT_LIST_HEAD(&node->upper); 2505 INIT_LIST_HEAD(&node->lower); 2506 RB_CLEAR_NODE(&node->rb_node); 2507 cache->nr_nodes++; 2508 node->level = level; 2509 node->bytenr = bytenr; 2510 2511 return node; 2512 } 2513 2514 struct btrfs_backref_edge *btrfs_backref_alloc_edge( 2515 struct btrfs_backref_cache *cache) 2516 { 2517 struct btrfs_backref_edge *edge; 2518 2519 edge = kzalloc(sizeof(*edge), GFP_NOFS); 2520 if (edge) 2521 cache->nr_edges++; 2522 return edge; 2523 } 2524 2525 /* 2526 * Drop the backref node from cache, also cleaning up all its 2527 * upper edges and any uncached nodes in the path. 2528 * 2529 * This cleanup happens bottom up, thus the node should either 2530 * be the lowest node in the cache or a detached node. 2531 */ 2532 void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache, 2533 struct btrfs_backref_node *node) 2534 { 2535 struct btrfs_backref_node *upper; 2536 struct btrfs_backref_edge *edge; 2537 2538 if (!node) 2539 return; 2540 2541 BUG_ON(!node->lowest && !node->detached); 2542 while (!list_empty(&node->upper)) { 2543 edge = list_entry(node->upper.next, struct btrfs_backref_edge, 2544 list[LOWER]); 2545 upper = edge->node[UPPER]; 2546 list_del(&edge->list[LOWER]); 2547 list_del(&edge->list[UPPER]); 2548 btrfs_backref_free_edge(cache, edge); 2549 2550 /* 2551 * Add the node to leaf node list if no other child block 2552 * cached. 2553 */ 2554 if (list_empty(&upper->lower)) { 2555 list_add_tail(&upper->lower, &cache->leaves); 2556 upper->lowest = 1; 2557 } 2558 } 2559 2560 btrfs_backref_drop_node(cache, node); 2561 } 2562 2563 /* 2564 * Release all nodes/edges from current cache 2565 */ 2566 void btrfs_backref_release_cache(struct btrfs_backref_cache *cache) 2567 { 2568 struct btrfs_backref_node *node; 2569 int i; 2570 2571 while (!list_empty(&cache->detached)) { 2572 node = list_entry(cache->detached.next, 2573 struct btrfs_backref_node, list); 2574 btrfs_backref_cleanup_node(cache, node); 2575 } 2576 2577 while (!list_empty(&cache->leaves)) { 2578 node = list_entry(cache->leaves.next, 2579 struct btrfs_backref_node, lower); 2580 btrfs_backref_cleanup_node(cache, node); 2581 } 2582 2583 cache->last_trans = 0; 2584 2585 for (i = 0; i < BTRFS_MAX_LEVEL; i++) 2586 ASSERT(list_empty(&cache->pending[i])); 2587 ASSERT(list_empty(&cache->pending_edge)); 2588 ASSERT(list_empty(&cache->useless_node)); 2589 ASSERT(list_empty(&cache->changed)); 2590 ASSERT(list_empty(&cache->detached)); 2591 ASSERT(RB_EMPTY_ROOT(&cache->rb_root)); 2592 ASSERT(!cache->nr_nodes); 2593 ASSERT(!cache->nr_edges); 2594 } 2595 2596 /* 2597 * Handle direct tree backref 2598 * 2599 * Direct tree backref means, the backref item shows its parent bytenr 2600 * directly. This is for SHARED_BLOCK_REF backref (keyed or inlined). 2601 * 2602 * @ref_key: The converted backref key. 2603 * For keyed backref, it's the item key. 2604 * For inlined backref, objectid is the bytenr, 2605 * type is btrfs_inline_ref_type, offset is 2606 * btrfs_inline_ref_offset. 2607 */ 2608 static int handle_direct_tree_backref(struct btrfs_backref_cache *cache, 2609 struct btrfs_key *ref_key, 2610 struct btrfs_backref_node *cur) 2611 { 2612 struct btrfs_backref_edge *edge; 2613 struct btrfs_backref_node *upper; 2614 struct rb_node *rb_node; 2615 2616 ASSERT(ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY); 2617 2618 /* Only reloc root uses backref pointing to itself */ 2619 if (ref_key->objectid == ref_key->offset) { 2620 struct btrfs_root *root; 2621 2622 cur->is_reloc_root = 1; 2623 /* Only reloc backref cache cares about a specific root */ 2624 if (cache->is_reloc) { 2625 root = find_reloc_root(cache->fs_info, cur->bytenr); 2626 if (!root) 2627 return -ENOENT; 2628 cur->root = root; 2629 } else { 2630 /* 2631 * For generic purpose backref cache, reloc root node 2632 * is useless. 2633 */ 2634 list_add(&cur->list, &cache->useless_node); 2635 } 2636 return 0; 2637 } 2638 2639 edge = btrfs_backref_alloc_edge(cache); 2640 if (!edge) 2641 return -ENOMEM; 2642 2643 rb_node = rb_simple_search(&cache->rb_root, ref_key->offset); 2644 if (!rb_node) { 2645 /* Parent node not yet cached */ 2646 upper = btrfs_backref_alloc_node(cache, ref_key->offset, 2647 cur->level + 1); 2648 if (!upper) { 2649 btrfs_backref_free_edge(cache, edge); 2650 return -ENOMEM; 2651 } 2652 2653 /* 2654 * Backrefs for the upper level block isn't cached, add the 2655 * block to pending list 2656 */ 2657 list_add_tail(&edge->list[UPPER], &cache->pending_edge); 2658 } else { 2659 /* Parent node already cached */ 2660 upper = rb_entry(rb_node, struct btrfs_backref_node, rb_node); 2661 ASSERT(upper->checked); 2662 INIT_LIST_HEAD(&edge->list[UPPER]); 2663 } 2664 btrfs_backref_link_edge(edge, cur, upper, LINK_LOWER); 2665 return 0; 2666 } 2667 2668 /* 2669 * Handle indirect tree backref 2670 * 2671 * Indirect tree backref means, we only know which tree the node belongs to. 2672 * We still need to do a tree search to find out the parents. This is for 2673 * TREE_BLOCK_REF backref (keyed or inlined). 2674 * 2675 * @ref_key: The same as @ref_key in handle_direct_tree_backref() 2676 * @tree_key: The first key of this tree block. 2677 * @path: A clean (released) path, to avoid allocating path every time 2678 * the function get called. 2679 */ 2680 static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache, 2681 struct btrfs_path *path, 2682 struct btrfs_key *ref_key, 2683 struct btrfs_key *tree_key, 2684 struct btrfs_backref_node *cur) 2685 { 2686 struct btrfs_fs_info *fs_info = cache->fs_info; 2687 struct btrfs_backref_node *upper; 2688 struct btrfs_backref_node *lower; 2689 struct btrfs_backref_edge *edge; 2690 struct extent_buffer *eb; 2691 struct btrfs_root *root; 2692 struct rb_node *rb_node; 2693 int level; 2694 bool need_check = true; 2695 int ret; 2696 2697 root = btrfs_get_fs_root(fs_info, ref_key->offset, false); 2698 if (IS_ERR(root)) 2699 return PTR_ERR(root); 2700 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) 2701 cur->cowonly = 1; 2702 2703 if (btrfs_root_level(&root->root_item) == cur->level) { 2704 /* Tree root */ 2705 ASSERT(btrfs_root_bytenr(&root->root_item) == cur->bytenr); 2706 /* 2707 * For reloc backref cache, we may ignore reloc root. But for 2708 * general purpose backref cache, we can't rely on 2709 * btrfs_should_ignore_reloc_root() as it may conflict with 2710 * current running relocation and lead to missing root. 2711 * 2712 * For general purpose backref cache, reloc root detection is 2713 * completely relying on direct backref (key->offset is parent 2714 * bytenr), thus only do such check for reloc cache. 2715 */ 2716 if (btrfs_should_ignore_reloc_root(root) && cache->is_reloc) { 2717 btrfs_put_root(root); 2718 list_add(&cur->list, &cache->useless_node); 2719 } else { 2720 cur->root = root; 2721 } 2722 return 0; 2723 } 2724 2725 level = cur->level + 1; 2726 2727 /* Search the tree to find parent blocks referring to the block */ 2728 path->search_commit_root = 1; 2729 path->skip_locking = 1; 2730 path->lowest_level = level; 2731 ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0); 2732 path->lowest_level = 0; 2733 if (ret < 0) { 2734 btrfs_put_root(root); 2735 return ret; 2736 } 2737 if (ret > 0 && path->slots[level] > 0) 2738 path->slots[level]--; 2739 2740 eb = path->nodes[level]; 2741 if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) { 2742 btrfs_err(fs_info, 2743 "couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)", 2744 cur->bytenr, level - 1, root->root_key.objectid, 2745 tree_key->objectid, tree_key->type, tree_key->offset); 2746 btrfs_put_root(root); 2747 ret = -ENOENT; 2748 goto out; 2749 } 2750 lower = cur; 2751 2752 /* Add all nodes and edges in the path */ 2753 for (; level < BTRFS_MAX_LEVEL; level++) { 2754 if (!path->nodes[level]) { 2755 ASSERT(btrfs_root_bytenr(&root->root_item) == 2756 lower->bytenr); 2757 /* Same as previous should_ignore_reloc_root() call */ 2758 if (btrfs_should_ignore_reloc_root(root) && 2759 cache->is_reloc) { 2760 btrfs_put_root(root); 2761 list_add(&lower->list, &cache->useless_node); 2762 } else { 2763 lower->root = root; 2764 } 2765 break; 2766 } 2767 2768 edge = btrfs_backref_alloc_edge(cache); 2769 if (!edge) { 2770 btrfs_put_root(root); 2771 ret = -ENOMEM; 2772 goto out; 2773 } 2774 2775 eb = path->nodes[level]; 2776 rb_node = rb_simple_search(&cache->rb_root, eb->start); 2777 if (!rb_node) { 2778 upper = btrfs_backref_alloc_node(cache, eb->start, 2779 lower->level + 1); 2780 if (!upper) { 2781 btrfs_put_root(root); 2782 btrfs_backref_free_edge(cache, edge); 2783 ret = -ENOMEM; 2784 goto out; 2785 } 2786 upper->owner = btrfs_header_owner(eb); 2787 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) 2788 upper->cowonly = 1; 2789 2790 /* 2791 * If we know the block isn't shared we can avoid 2792 * checking its backrefs. 2793 */ 2794 if (btrfs_block_can_be_shared(root, eb)) 2795 upper->checked = 0; 2796 else 2797 upper->checked = 1; 2798 2799 /* 2800 * Add the block to pending list if we need to check its 2801 * backrefs, we only do this once while walking up a 2802 * tree as we will catch anything else later on. 2803 */ 2804 if (!upper->checked && need_check) { 2805 need_check = false; 2806 list_add_tail(&edge->list[UPPER], 2807 &cache->pending_edge); 2808 } else { 2809 if (upper->checked) 2810 need_check = true; 2811 INIT_LIST_HEAD(&edge->list[UPPER]); 2812 } 2813 } else { 2814 upper = rb_entry(rb_node, struct btrfs_backref_node, 2815 rb_node); 2816 ASSERT(upper->checked); 2817 INIT_LIST_HEAD(&edge->list[UPPER]); 2818 if (!upper->owner) 2819 upper->owner = btrfs_header_owner(eb); 2820 } 2821 btrfs_backref_link_edge(edge, lower, upper, LINK_LOWER); 2822 2823 if (rb_node) { 2824 btrfs_put_root(root); 2825 break; 2826 } 2827 lower = upper; 2828 upper = NULL; 2829 } 2830 out: 2831 btrfs_release_path(path); 2832 return ret; 2833 } 2834 2835 /* 2836 * Add backref node @cur into @cache. 2837 * 2838 * NOTE: Even if the function returned 0, @cur is not yet cached as its upper 2839 * links aren't yet bi-directional. Needs to finish such links. 2840 * Use btrfs_backref_finish_upper_links() to finish such linkage. 2841 * 2842 * @path: Released path for indirect tree backref lookup 2843 * @iter: Released backref iter for extent tree search 2844 * @node_key: The first key of the tree block 2845 */ 2846 int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache, 2847 struct btrfs_path *path, 2848 struct btrfs_backref_iter *iter, 2849 struct btrfs_key *node_key, 2850 struct btrfs_backref_node *cur) 2851 { 2852 struct btrfs_fs_info *fs_info = cache->fs_info; 2853 struct btrfs_backref_edge *edge; 2854 struct btrfs_backref_node *exist; 2855 int ret; 2856 2857 ret = btrfs_backref_iter_start(iter, cur->bytenr); 2858 if (ret < 0) 2859 return ret; 2860 /* 2861 * We skip the first btrfs_tree_block_info, as we don't use the key 2862 * stored in it, but fetch it from the tree block 2863 */ 2864 if (btrfs_backref_has_tree_block_info(iter)) { 2865 ret = btrfs_backref_iter_next(iter); 2866 if (ret < 0) 2867 goto out; 2868 /* No extra backref? This means the tree block is corrupted */ 2869 if (ret > 0) { 2870 ret = -EUCLEAN; 2871 goto out; 2872 } 2873 } 2874 WARN_ON(cur->checked); 2875 if (!list_empty(&cur->upper)) { 2876 /* 2877 * The backref was added previously when processing backref of 2878 * type BTRFS_TREE_BLOCK_REF_KEY 2879 */ 2880 ASSERT(list_is_singular(&cur->upper)); 2881 edge = list_entry(cur->upper.next, struct btrfs_backref_edge, 2882 list[LOWER]); 2883 ASSERT(list_empty(&edge->list[UPPER])); 2884 exist = edge->node[UPPER]; 2885 /* 2886 * Add the upper level block to pending list if we need check 2887 * its backrefs 2888 */ 2889 if (!exist->checked) 2890 list_add_tail(&edge->list[UPPER], &cache->pending_edge); 2891 } else { 2892 exist = NULL; 2893 } 2894 2895 for (; ret == 0; ret = btrfs_backref_iter_next(iter)) { 2896 struct extent_buffer *eb; 2897 struct btrfs_key key; 2898 int type; 2899 2900 cond_resched(); 2901 eb = btrfs_backref_get_eb(iter); 2902 2903 key.objectid = iter->bytenr; 2904 if (btrfs_backref_iter_is_inline_ref(iter)) { 2905 struct btrfs_extent_inline_ref *iref; 2906 2907 /* Update key for inline backref */ 2908 iref = (struct btrfs_extent_inline_ref *) 2909 ((unsigned long)iter->cur_ptr); 2910 type = btrfs_get_extent_inline_ref_type(eb, iref, 2911 BTRFS_REF_TYPE_BLOCK); 2912 if (type == BTRFS_REF_TYPE_INVALID) { 2913 ret = -EUCLEAN; 2914 goto out; 2915 } 2916 key.type = type; 2917 key.offset = btrfs_extent_inline_ref_offset(eb, iref); 2918 } else { 2919 key.type = iter->cur_key.type; 2920 key.offset = iter->cur_key.offset; 2921 } 2922 2923 /* 2924 * Parent node found and matches current inline ref, no need to 2925 * rebuild this node for this inline ref 2926 */ 2927 if (exist && 2928 ((key.type == BTRFS_TREE_BLOCK_REF_KEY && 2929 exist->owner == key.offset) || 2930 (key.type == BTRFS_SHARED_BLOCK_REF_KEY && 2931 exist->bytenr == key.offset))) { 2932 exist = NULL; 2933 continue; 2934 } 2935 2936 /* SHARED_BLOCK_REF means key.offset is the parent bytenr */ 2937 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) { 2938 ret = handle_direct_tree_backref(cache, &key, cur); 2939 if (ret < 0) 2940 goto out; 2941 continue; 2942 } else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) { 2943 ret = -EINVAL; 2944 btrfs_print_v0_err(fs_info); 2945 btrfs_handle_fs_error(fs_info, ret, NULL); 2946 goto out; 2947 } else if (key.type != BTRFS_TREE_BLOCK_REF_KEY) { 2948 continue; 2949 } 2950 2951 /* 2952 * key.type == BTRFS_TREE_BLOCK_REF_KEY, inline ref offset 2953 * means the root objectid. We need to search the tree to get 2954 * its parent bytenr. 2955 */ 2956 ret = handle_indirect_tree_backref(cache, path, &key, node_key, 2957 cur); 2958 if (ret < 0) 2959 goto out; 2960 } 2961 ret = 0; 2962 cur->checked = 1; 2963 WARN_ON(exist); 2964 out: 2965 btrfs_backref_iter_release(iter); 2966 return ret; 2967 } 2968 2969 /* 2970 * Finish the upwards linkage created by btrfs_backref_add_tree_node() 2971 */ 2972 int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache, 2973 struct btrfs_backref_node *start) 2974 { 2975 struct list_head *useless_node = &cache->useless_node; 2976 struct btrfs_backref_edge *edge; 2977 struct rb_node *rb_node; 2978 LIST_HEAD(pending_edge); 2979 2980 ASSERT(start->checked); 2981 2982 /* Insert this node to cache if it's not COW-only */ 2983 if (!start->cowonly) { 2984 rb_node = rb_simple_insert(&cache->rb_root, start->bytenr, 2985 &start->rb_node); 2986 if (rb_node) 2987 btrfs_backref_panic(cache->fs_info, start->bytenr, 2988 -EEXIST); 2989 list_add_tail(&start->lower, &cache->leaves); 2990 } 2991 2992 /* 2993 * Use breadth first search to iterate all related edges. 2994 * 2995 * The starting points are all the edges of this node 2996 */ 2997 list_for_each_entry(edge, &start->upper, list[LOWER]) 2998 list_add_tail(&edge->list[UPPER], &pending_edge); 2999 3000 while (!list_empty(&pending_edge)) { 3001 struct btrfs_backref_node *upper; 3002 struct btrfs_backref_node *lower; 3003 3004 edge = list_first_entry(&pending_edge, 3005 struct btrfs_backref_edge, list[UPPER]); 3006 list_del_init(&edge->list[UPPER]); 3007 upper = edge->node[UPPER]; 3008 lower = edge->node[LOWER]; 3009 3010 /* Parent is detached, no need to keep any edges */ 3011 if (upper->detached) { 3012 list_del(&edge->list[LOWER]); 3013 btrfs_backref_free_edge(cache, edge); 3014 3015 /* Lower node is orphan, queue for cleanup */ 3016 if (list_empty(&lower->upper)) 3017 list_add(&lower->list, useless_node); 3018 continue; 3019 } 3020 3021 /* 3022 * All new nodes added in current build_backref_tree() haven't 3023 * been linked to the cache rb tree. 3024 * So if we have upper->rb_node populated, this means a cache 3025 * hit. We only need to link the edge, as @upper and all its 3026 * parents have already been linked. 3027 */ 3028 if (!RB_EMPTY_NODE(&upper->rb_node)) { 3029 if (upper->lowest) { 3030 list_del_init(&upper->lower); 3031 upper->lowest = 0; 3032 } 3033 3034 list_add_tail(&edge->list[UPPER], &upper->lower); 3035 continue; 3036 } 3037 3038 /* Sanity check, we shouldn't have any unchecked nodes */ 3039 if (!upper->checked) { 3040 ASSERT(0); 3041 return -EUCLEAN; 3042 } 3043 3044 /* Sanity check, COW-only node has non-COW-only parent */ 3045 if (start->cowonly != upper->cowonly) { 3046 ASSERT(0); 3047 return -EUCLEAN; 3048 } 3049 3050 /* Only cache non-COW-only (subvolume trees) tree blocks */ 3051 if (!upper->cowonly) { 3052 rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr, 3053 &upper->rb_node); 3054 if (rb_node) { 3055 btrfs_backref_panic(cache->fs_info, 3056 upper->bytenr, -EEXIST); 3057 return -EUCLEAN; 3058 } 3059 } 3060 3061 list_add_tail(&edge->list[UPPER], &upper->lower); 3062 3063 /* 3064 * Also queue all the parent edges of this uncached node 3065 * to finish the upper linkage 3066 */ 3067 list_for_each_entry(edge, &upper->upper, list[LOWER]) 3068 list_add_tail(&edge->list[UPPER], &pending_edge); 3069 } 3070 return 0; 3071 } 3072 3073 void btrfs_backref_error_cleanup(struct btrfs_backref_cache *cache, 3074 struct btrfs_backref_node *node) 3075 { 3076 struct btrfs_backref_node *lower; 3077 struct btrfs_backref_node *upper; 3078 struct btrfs_backref_edge *edge; 3079 3080 while (!list_empty(&cache->useless_node)) { 3081 lower = list_first_entry(&cache->useless_node, 3082 struct btrfs_backref_node, list); 3083 list_del_init(&lower->list); 3084 } 3085 while (!list_empty(&cache->pending_edge)) { 3086 edge = list_first_entry(&cache->pending_edge, 3087 struct btrfs_backref_edge, list[UPPER]); 3088 list_del(&edge->list[UPPER]); 3089 list_del(&edge->list[LOWER]); 3090 lower = edge->node[LOWER]; 3091 upper = edge->node[UPPER]; 3092 btrfs_backref_free_edge(cache, edge); 3093 3094 /* 3095 * Lower is no longer linked to any upper backref nodes and 3096 * isn't in the cache, we can free it ourselves. 3097 */ 3098 if (list_empty(&lower->upper) && 3099 RB_EMPTY_NODE(&lower->rb_node)) 3100 list_add(&lower->list, &cache->useless_node); 3101 3102 if (!RB_EMPTY_NODE(&upper->rb_node)) 3103 continue; 3104 3105 /* Add this guy's upper edges to the list to process */ 3106 list_for_each_entry(edge, &upper->upper, list[LOWER]) 3107 list_add_tail(&edge->list[UPPER], 3108 &cache->pending_edge); 3109 if (list_empty(&upper->upper)) 3110 list_add(&upper->list, &cache->useless_node); 3111 } 3112 3113 while (!list_empty(&cache->useless_node)) { 3114 lower = list_first_entry(&cache->useless_node, 3115 struct btrfs_backref_node, list); 3116 list_del_init(&lower->list); 3117 if (lower == node) 3118 node = NULL; 3119 btrfs_backref_drop_node(cache, lower); 3120 } 3121 3122 btrfs_backref_cleanup_node(cache, node); 3123 ASSERT(list_empty(&cache->useless_node) && 3124 list_empty(&cache->pending_edge)); 3125 } 3126