1 /* 2 * Copyright (C) 2011 STRATO. All rights reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public 6 * License v2 as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public 14 * License along with this program; if not, write to the 15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 16 * Boston, MA 021110-1307, USA. 17 */ 18 19 #include <linux/vmalloc.h> 20 #include "ctree.h" 21 #include "disk-io.h" 22 #include "backref.h" 23 #include "ulist.h" 24 #include "transaction.h" 25 #include "delayed-ref.h" 26 #include "locking.h" 27 28 struct extent_inode_elem { 29 u64 inum; 30 u64 offset; 31 struct extent_inode_elem *next; 32 }; 33 34 static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb, 35 struct btrfs_file_extent_item *fi, 36 u64 extent_item_pos, 37 struct extent_inode_elem **eie) 38 { 39 u64 data_offset; 40 u64 data_len; 41 struct extent_inode_elem *e; 42 43 data_offset = btrfs_file_extent_offset(eb, fi); 44 data_len = btrfs_file_extent_num_bytes(eb, fi); 45 46 if (extent_item_pos < data_offset || 47 extent_item_pos >= data_offset + data_len) 48 return 1; 49 50 e = kmalloc(sizeof(*e), GFP_NOFS); 51 if (!e) 52 return -ENOMEM; 53 54 e->next = *eie; 55 e->inum = key->objectid; 56 e->offset = key->offset + (extent_item_pos - data_offset); 57 *eie = e; 58 59 return 0; 60 } 61 62 static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte, 63 u64 extent_item_pos, 64 struct extent_inode_elem **eie) 65 { 66 u64 disk_byte; 67 struct btrfs_key key; 68 struct btrfs_file_extent_item *fi; 69 int slot; 70 int nritems; 71 int extent_type; 72 int ret; 73 74 /* 75 * from the shared data ref, we only have the leaf but we need 76 * the key. thus, we must look into all items and see that we 77 * find one (some) with a reference to our extent item. 78 */ 79 nritems = btrfs_header_nritems(eb); 80 for (slot = 0; slot < nritems; ++slot) { 81 btrfs_item_key_to_cpu(eb, &key, slot); 82 if (key.type != BTRFS_EXTENT_DATA_KEY) 83 continue; 84 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 85 extent_type = btrfs_file_extent_type(eb, fi); 86 if (extent_type == BTRFS_FILE_EXTENT_INLINE) 87 continue; 88 /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */ 89 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi); 90 if (disk_byte != wanted_disk_byte) 91 continue; 92 93 ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie); 94 if (ret < 0) 95 return ret; 96 } 97 98 return 0; 99 } 100 101 /* 102 * this structure records all encountered refs on the way up to the root 103 */ 104 struct __prelim_ref { 105 struct list_head list; 106 u64 root_id; 107 struct btrfs_key key_for_search; 108 int level; 109 int count; 110 struct extent_inode_elem *inode_list; 111 u64 parent; 112 u64 wanted_disk_byte; 113 }; 114 115 /* 116 * the rules for all callers of this function are: 117 * - obtaining the parent is the goal 118 * - if you add a key, you must know that it is a correct key 119 * - if you cannot add the parent or a correct key, then we will look into the 120 * block later to set a correct key 121 * 122 * delayed refs 123 * ============ 124 * backref type | shared | indirect | shared | indirect 125 * information | tree | tree | data | data 126 * --------------------+--------+----------+--------+---------- 127 * parent logical | y | - | - | - 128 * key to resolve | - | y | y | y 129 * tree block logical | - | - | - | - 130 * root for resolving | y | y | y | y 131 * 132 * - column 1: we've the parent -> done 133 * - column 2, 3, 4: we use the key to find the parent 134 * 135 * on disk refs (inline or keyed) 136 * ============================== 137 * backref type | shared | indirect | shared | indirect 138 * information | tree | tree | data | data 139 * --------------------+--------+----------+--------+---------- 140 * parent logical | y | - | y | - 141 * key to resolve | - | - | - | y 142 * tree block logical | y | y | y | y 143 * root for resolving | - | y | y | y 144 * 145 * - column 1, 3: we've the parent -> done 146 * - column 2: we take the first key from the block to find the parent 147 * (see __add_missing_keys) 148 * - column 4: we use the key to find the parent 149 * 150 * additional information that's available but not required to find the parent 151 * block might help in merging entries to gain some speed. 152 */ 153 154 static int __add_prelim_ref(struct list_head *head, u64 root_id, 155 struct btrfs_key *key, int level, 156 u64 parent, u64 wanted_disk_byte, int count) 157 { 158 struct __prelim_ref *ref; 159 160 /* in case we're adding delayed refs, we're holding the refs spinlock */ 161 ref = kmalloc(sizeof(*ref), GFP_ATOMIC); 162 if (!ref) 163 return -ENOMEM; 164 165 ref->root_id = root_id; 166 if (key) 167 ref->key_for_search = *key; 168 else 169 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search)); 170 171 ref->inode_list = NULL; 172 ref->level = level; 173 ref->count = count; 174 ref->parent = parent; 175 ref->wanted_disk_byte = wanted_disk_byte; 176 list_add_tail(&ref->list, head); 177 178 return 0; 179 } 180 181 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, 182 struct ulist *parents, int level, 183 struct btrfs_key *key_for_search, u64 time_seq, 184 u64 wanted_disk_byte, 185 const u64 *extent_item_pos) 186 { 187 int ret = 0; 188 int slot; 189 struct extent_buffer *eb; 190 struct btrfs_key key; 191 struct btrfs_file_extent_item *fi; 192 struct extent_inode_elem *eie = NULL; 193 u64 disk_byte; 194 195 if (level != 0) { 196 eb = path->nodes[level]; 197 ret = ulist_add(parents, eb->start, 0, GFP_NOFS); 198 if (ret < 0) 199 return ret; 200 return 0; 201 } 202 203 /* 204 * We normally enter this function with the path already pointing to 205 * the first item to check. But sometimes, we may enter it with 206 * slot==nritems. In that case, go to the next leaf before we continue. 207 */ 208 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) 209 ret = btrfs_next_old_leaf(root, path, time_seq); 210 211 while (!ret) { 212 eb = path->nodes[0]; 213 slot = path->slots[0]; 214 215 btrfs_item_key_to_cpu(eb, &key, slot); 216 217 if (key.objectid != key_for_search->objectid || 218 key.type != BTRFS_EXTENT_DATA_KEY) 219 break; 220 221 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); 222 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi); 223 224 if (disk_byte == wanted_disk_byte) { 225 eie = NULL; 226 if (extent_item_pos) { 227 ret = check_extent_in_eb(&key, eb, fi, 228 *extent_item_pos, 229 &eie); 230 if (ret < 0) 231 break; 232 } 233 if (!ret) { 234 ret = ulist_add(parents, eb->start, 235 (uintptr_t)eie, GFP_NOFS); 236 if (ret < 0) 237 break; 238 if (!extent_item_pos) { 239 ret = btrfs_next_old_leaf(root, path, 240 time_seq); 241 continue; 242 } 243 } 244 } 245 ret = btrfs_next_old_item(root, path, time_seq); 246 } 247 248 if (ret > 0) 249 ret = 0; 250 return ret; 251 } 252 253 /* 254 * resolve an indirect backref in the form (root_id, key, level) 255 * to a logical address 256 */ 257 static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info, 258 int search_commit_root, 259 u64 time_seq, 260 struct __prelim_ref *ref, 261 struct ulist *parents, 262 const u64 *extent_item_pos) 263 { 264 struct btrfs_path *path; 265 struct btrfs_root *root; 266 struct btrfs_key root_key; 267 struct extent_buffer *eb; 268 int ret = 0; 269 int root_level; 270 int level = ref->level; 271 272 path = btrfs_alloc_path(); 273 if (!path) 274 return -ENOMEM; 275 path->search_commit_root = !!search_commit_root; 276 277 root_key.objectid = ref->root_id; 278 root_key.type = BTRFS_ROOT_ITEM_KEY; 279 root_key.offset = (u64)-1; 280 root = btrfs_read_fs_root_no_name(fs_info, &root_key); 281 if (IS_ERR(root)) { 282 ret = PTR_ERR(root); 283 goto out; 284 } 285 286 root_level = btrfs_old_root_level(root, time_seq); 287 288 if (root_level + 1 == level) 289 goto out; 290 291 path->lowest_level = level; 292 ret = btrfs_search_old_slot(root, &ref->key_for_search, path, time_seq); 293 pr_debug("search slot in root %llu (level %d, ref count %d) returned " 294 "%d for key (%llu %u %llu)\n", 295 (unsigned long long)ref->root_id, level, ref->count, ret, 296 (unsigned long long)ref->key_for_search.objectid, 297 ref->key_for_search.type, 298 (unsigned long long)ref->key_for_search.offset); 299 if (ret < 0) 300 goto out; 301 302 eb = path->nodes[level]; 303 while (!eb) { 304 if (!level) { 305 WARN_ON(1); 306 ret = 1; 307 goto out; 308 } 309 level--; 310 eb = path->nodes[level]; 311 } 312 313 ret = add_all_parents(root, path, parents, level, &ref->key_for_search, 314 time_seq, ref->wanted_disk_byte, 315 extent_item_pos); 316 out: 317 btrfs_free_path(path); 318 return ret; 319 } 320 321 /* 322 * resolve all indirect backrefs from the list 323 */ 324 static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info, 325 int search_commit_root, u64 time_seq, 326 struct list_head *head, 327 const u64 *extent_item_pos) 328 { 329 int err; 330 int ret = 0; 331 struct __prelim_ref *ref; 332 struct __prelim_ref *ref_safe; 333 struct __prelim_ref *new_ref; 334 struct ulist *parents; 335 struct ulist_node *node; 336 struct ulist_iterator uiter; 337 338 parents = ulist_alloc(GFP_NOFS); 339 if (!parents) 340 return -ENOMEM; 341 342 /* 343 * _safe allows us to insert directly after the current item without 344 * iterating over the newly inserted items. 345 * we're also allowed to re-assign ref during iteration. 346 */ 347 list_for_each_entry_safe(ref, ref_safe, head, list) { 348 if (ref->parent) /* already direct */ 349 continue; 350 if (ref->count == 0) 351 continue; 352 err = __resolve_indirect_ref(fs_info, search_commit_root, 353 time_seq, ref, parents, 354 extent_item_pos); 355 if (err) { 356 if (ret == 0) 357 ret = err; 358 continue; 359 } 360 361 /* we put the first parent into the ref at hand */ 362 ULIST_ITER_INIT(&uiter); 363 node = ulist_next(parents, &uiter); 364 ref->parent = node ? node->val : 0; 365 ref->inode_list = node ? 366 (struct extent_inode_elem *)(uintptr_t)node->aux : 0; 367 368 /* additional parents require new refs being added here */ 369 while ((node = ulist_next(parents, &uiter))) { 370 new_ref = kmalloc(sizeof(*new_ref), GFP_NOFS); 371 if (!new_ref) { 372 ret = -ENOMEM; 373 break; 374 } 375 memcpy(new_ref, ref, sizeof(*ref)); 376 new_ref->parent = node->val; 377 new_ref->inode_list = (struct extent_inode_elem *) 378 (uintptr_t)node->aux; 379 list_add(&new_ref->list, &ref->list); 380 } 381 ulist_reinit(parents); 382 } 383 384 ulist_free(parents); 385 return ret; 386 } 387 388 static inline int ref_for_same_block(struct __prelim_ref *ref1, 389 struct __prelim_ref *ref2) 390 { 391 if (ref1->level != ref2->level) 392 return 0; 393 if (ref1->root_id != ref2->root_id) 394 return 0; 395 if (ref1->key_for_search.type != ref2->key_for_search.type) 396 return 0; 397 if (ref1->key_for_search.objectid != ref2->key_for_search.objectid) 398 return 0; 399 if (ref1->key_for_search.offset != ref2->key_for_search.offset) 400 return 0; 401 if (ref1->parent != ref2->parent) 402 return 0; 403 404 return 1; 405 } 406 407 /* 408 * read tree blocks and add keys where required. 409 */ 410 static int __add_missing_keys(struct btrfs_fs_info *fs_info, 411 struct list_head *head) 412 { 413 struct list_head *pos; 414 struct extent_buffer *eb; 415 416 list_for_each(pos, head) { 417 struct __prelim_ref *ref; 418 ref = list_entry(pos, struct __prelim_ref, list); 419 420 if (ref->parent) 421 continue; 422 if (ref->key_for_search.type) 423 continue; 424 BUG_ON(!ref->wanted_disk_byte); 425 eb = read_tree_block(fs_info->tree_root, ref->wanted_disk_byte, 426 fs_info->tree_root->leafsize, 0); 427 BUG_ON(!eb); 428 btrfs_tree_read_lock(eb); 429 if (btrfs_header_level(eb) == 0) 430 btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0); 431 else 432 btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0); 433 btrfs_tree_read_unlock(eb); 434 free_extent_buffer(eb); 435 } 436 return 0; 437 } 438 439 /* 440 * merge two lists of backrefs and adjust counts accordingly 441 * 442 * mode = 1: merge identical keys, if key is set 443 * FIXME: if we add more keys in __add_prelim_ref, we can merge more here. 444 * additionally, we could even add a key range for the blocks we 445 * looked into to merge even more (-> replace unresolved refs by those 446 * having a parent). 447 * mode = 2: merge identical parents 448 */ 449 static int __merge_refs(struct list_head *head, int mode) 450 { 451 struct list_head *pos1; 452 453 list_for_each(pos1, head) { 454 struct list_head *n2; 455 struct list_head *pos2; 456 struct __prelim_ref *ref1; 457 458 ref1 = list_entry(pos1, struct __prelim_ref, list); 459 460 for (pos2 = pos1->next, n2 = pos2->next; pos2 != head; 461 pos2 = n2, n2 = pos2->next) { 462 struct __prelim_ref *ref2; 463 struct __prelim_ref *xchg; 464 struct extent_inode_elem *eie; 465 466 ref2 = list_entry(pos2, struct __prelim_ref, list); 467 468 if (mode == 1) { 469 if (!ref_for_same_block(ref1, ref2)) 470 continue; 471 if (!ref1->parent && ref2->parent) { 472 xchg = ref1; 473 ref1 = ref2; 474 ref2 = xchg; 475 } 476 } else { 477 if (ref1->parent != ref2->parent) 478 continue; 479 } 480 481 eie = ref1->inode_list; 482 while (eie && eie->next) 483 eie = eie->next; 484 if (eie) 485 eie->next = ref2->inode_list; 486 else 487 ref1->inode_list = ref2->inode_list; 488 ref1->count += ref2->count; 489 490 list_del(&ref2->list); 491 kfree(ref2); 492 } 493 494 } 495 return 0; 496 } 497 498 /* 499 * add all currently queued delayed refs from this head whose seq nr is 500 * smaller or equal that seq to the list 501 */ 502 static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, 503 struct list_head *prefs) 504 { 505 struct btrfs_delayed_extent_op *extent_op = head->extent_op; 506 struct rb_node *n = &head->node.rb_node; 507 struct btrfs_key key; 508 struct btrfs_key op_key = {0}; 509 int sgn; 510 int ret = 0; 511 512 if (extent_op && extent_op->update_key) 513 btrfs_disk_key_to_cpu(&op_key, &extent_op->key); 514 515 while ((n = rb_prev(n))) { 516 struct btrfs_delayed_ref_node *node; 517 node = rb_entry(n, struct btrfs_delayed_ref_node, 518 rb_node); 519 if (node->bytenr != head->node.bytenr) 520 break; 521 WARN_ON(node->is_head); 522 523 if (node->seq > seq) 524 continue; 525 526 switch (node->action) { 527 case BTRFS_ADD_DELAYED_EXTENT: 528 case BTRFS_UPDATE_DELAYED_HEAD: 529 WARN_ON(1); 530 continue; 531 case BTRFS_ADD_DELAYED_REF: 532 sgn = 1; 533 break; 534 case BTRFS_DROP_DELAYED_REF: 535 sgn = -1; 536 break; 537 default: 538 BUG_ON(1); 539 } 540 switch (node->type) { 541 case BTRFS_TREE_BLOCK_REF_KEY: { 542 struct btrfs_delayed_tree_ref *ref; 543 544 ref = btrfs_delayed_node_to_tree_ref(node); 545 ret = __add_prelim_ref(prefs, ref->root, &op_key, 546 ref->level + 1, 0, node->bytenr, 547 node->ref_mod * sgn); 548 break; 549 } 550 case BTRFS_SHARED_BLOCK_REF_KEY: { 551 struct btrfs_delayed_tree_ref *ref; 552 553 ref = btrfs_delayed_node_to_tree_ref(node); 554 ret = __add_prelim_ref(prefs, ref->root, NULL, 555 ref->level + 1, ref->parent, 556 node->bytenr, 557 node->ref_mod * sgn); 558 break; 559 } 560 case BTRFS_EXTENT_DATA_REF_KEY: { 561 struct btrfs_delayed_data_ref *ref; 562 ref = btrfs_delayed_node_to_data_ref(node); 563 564 key.objectid = ref->objectid; 565 key.type = BTRFS_EXTENT_DATA_KEY; 566 key.offset = ref->offset; 567 ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0, 568 node->bytenr, 569 node->ref_mod * sgn); 570 break; 571 } 572 case BTRFS_SHARED_DATA_REF_KEY: { 573 struct btrfs_delayed_data_ref *ref; 574 575 ref = btrfs_delayed_node_to_data_ref(node); 576 577 key.objectid = ref->objectid; 578 key.type = BTRFS_EXTENT_DATA_KEY; 579 key.offset = ref->offset; 580 ret = __add_prelim_ref(prefs, ref->root, &key, 0, 581 ref->parent, node->bytenr, 582 node->ref_mod * sgn); 583 break; 584 } 585 default: 586 WARN_ON(1); 587 } 588 BUG_ON(ret); 589 } 590 591 return 0; 592 } 593 594 /* 595 * add all inline backrefs for bytenr to the list 596 */ 597 static int __add_inline_refs(struct btrfs_fs_info *fs_info, 598 struct btrfs_path *path, u64 bytenr, 599 int *info_level, struct list_head *prefs) 600 { 601 int ret = 0; 602 int slot; 603 struct extent_buffer *leaf; 604 struct btrfs_key key; 605 unsigned long ptr; 606 unsigned long end; 607 struct btrfs_extent_item *ei; 608 u64 flags; 609 u64 item_size; 610 611 /* 612 * enumerate all inline refs 613 */ 614 leaf = path->nodes[0]; 615 slot = path->slots[0]; 616 617 item_size = btrfs_item_size_nr(leaf, slot); 618 BUG_ON(item_size < sizeof(*ei)); 619 620 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); 621 flags = btrfs_extent_flags(leaf, ei); 622 623 ptr = (unsigned long)(ei + 1); 624 end = (unsigned long)ei + item_size; 625 626 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { 627 struct btrfs_tree_block_info *info; 628 629 info = (struct btrfs_tree_block_info *)ptr; 630 *info_level = btrfs_tree_block_level(leaf, info); 631 ptr += sizeof(struct btrfs_tree_block_info); 632 BUG_ON(ptr > end); 633 } else { 634 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA)); 635 } 636 637 while (ptr < end) { 638 struct btrfs_extent_inline_ref *iref; 639 u64 offset; 640 int type; 641 642 iref = (struct btrfs_extent_inline_ref *)ptr; 643 type = btrfs_extent_inline_ref_type(leaf, iref); 644 offset = btrfs_extent_inline_ref_offset(leaf, iref); 645 646 switch (type) { 647 case BTRFS_SHARED_BLOCK_REF_KEY: 648 ret = __add_prelim_ref(prefs, 0, NULL, 649 *info_level + 1, offset, 650 bytenr, 1); 651 break; 652 case BTRFS_SHARED_DATA_REF_KEY: { 653 struct btrfs_shared_data_ref *sdref; 654 int count; 655 656 sdref = (struct btrfs_shared_data_ref *)(iref + 1); 657 count = btrfs_shared_data_ref_count(leaf, sdref); 658 ret = __add_prelim_ref(prefs, 0, NULL, 0, offset, 659 bytenr, count); 660 break; 661 } 662 case BTRFS_TREE_BLOCK_REF_KEY: 663 ret = __add_prelim_ref(prefs, offset, NULL, 664 *info_level + 1, 0, 665 bytenr, 1); 666 break; 667 case BTRFS_EXTENT_DATA_REF_KEY: { 668 struct btrfs_extent_data_ref *dref; 669 int count; 670 u64 root; 671 672 dref = (struct btrfs_extent_data_ref *)(&iref->offset); 673 count = btrfs_extent_data_ref_count(leaf, dref); 674 key.objectid = btrfs_extent_data_ref_objectid(leaf, 675 dref); 676 key.type = BTRFS_EXTENT_DATA_KEY; 677 key.offset = btrfs_extent_data_ref_offset(leaf, dref); 678 root = btrfs_extent_data_ref_root(leaf, dref); 679 ret = __add_prelim_ref(prefs, root, &key, 0, 0, 680 bytenr, count); 681 break; 682 } 683 default: 684 WARN_ON(1); 685 } 686 BUG_ON(ret); 687 ptr += btrfs_extent_inline_ref_size(type); 688 } 689 690 return 0; 691 } 692 693 /* 694 * add all non-inline backrefs for bytenr to the list 695 */ 696 static int __add_keyed_refs(struct btrfs_fs_info *fs_info, 697 struct btrfs_path *path, u64 bytenr, 698 int info_level, struct list_head *prefs) 699 { 700 struct btrfs_root *extent_root = fs_info->extent_root; 701 int ret; 702 int slot; 703 struct extent_buffer *leaf; 704 struct btrfs_key key; 705 706 while (1) { 707 ret = btrfs_next_item(extent_root, path); 708 if (ret < 0) 709 break; 710 if (ret) { 711 ret = 0; 712 break; 713 } 714 715 slot = path->slots[0]; 716 leaf = path->nodes[0]; 717 btrfs_item_key_to_cpu(leaf, &key, slot); 718 719 if (key.objectid != bytenr) 720 break; 721 if (key.type < BTRFS_TREE_BLOCK_REF_KEY) 722 continue; 723 if (key.type > BTRFS_SHARED_DATA_REF_KEY) 724 break; 725 726 switch (key.type) { 727 case BTRFS_SHARED_BLOCK_REF_KEY: 728 ret = __add_prelim_ref(prefs, 0, NULL, 729 info_level + 1, key.offset, 730 bytenr, 1); 731 break; 732 case BTRFS_SHARED_DATA_REF_KEY: { 733 struct btrfs_shared_data_ref *sdref; 734 int count; 735 736 sdref = btrfs_item_ptr(leaf, slot, 737 struct btrfs_shared_data_ref); 738 count = btrfs_shared_data_ref_count(leaf, sdref); 739 ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset, 740 bytenr, count); 741 break; 742 } 743 case BTRFS_TREE_BLOCK_REF_KEY: 744 ret = __add_prelim_ref(prefs, key.offset, NULL, 745 info_level + 1, 0, 746 bytenr, 1); 747 break; 748 case BTRFS_EXTENT_DATA_REF_KEY: { 749 struct btrfs_extent_data_ref *dref; 750 int count; 751 u64 root; 752 753 dref = btrfs_item_ptr(leaf, slot, 754 struct btrfs_extent_data_ref); 755 count = btrfs_extent_data_ref_count(leaf, dref); 756 key.objectid = btrfs_extent_data_ref_objectid(leaf, 757 dref); 758 key.type = BTRFS_EXTENT_DATA_KEY; 759 key.offset = btrfs_extent_data_ref_offset(leaf, dref); 760 root = btrfs_extent_data_ref_root(leaf, dref); 761 ret = __add_prelim_ref(prefs, root, &key, 0, 0, 762 bytenr, count); 763 break; 764 } 765 default: 766 WARN_ON(1); 767 } 768 BUG_ON(ret); 769 } 770 771 return ret; 772 } 773 774 /* 775 * this adds all existing backrefs (inline backrefs, backrefs and delayed 776 * refs) for the given bytenr to the refs list, merges duplicates and resolves 777 * indirect refs to their parent bytenr. 778 * When roots are found, they're added to the roots list 779 * 780 * FIXME some caching might speed things up 781 */ 782 static int find_parent_nodes(struct btrfs_trans_handle *trans, 783 struct btrfs_fs_info *fs_info, u64 bytenr, 784 u64 time_seq, struct ulist *refs, 785 struct ulist *roots, const u64 *extent_item_pos) 786 { 787 struct btrfs_key key; 788 struct btrfs_path *path; 789 struct btrfs_delayed_ref_root *delayed_refs = NULL; 790 struct btrfs_delayed_ref_head *head; 791 int info_level = 0; 792 int ret; 793 int search_commit_root = (trans == BTRFS_BACKREF_SEARCH_COMMIT_ROOT); 794 struct list_head prefs_delayed; 795 struct list_head prefs; 796 struct __prelim_ref *ref; 797 798 INIT_LIST_HEAD(&prefs); 799 INIT_LIST_HEAD(&prefs_delayed); 800 801 key.objectid = bytenr; 802 key.type = BTRFS_EXTENT_ITEM_KEY; 803 key.offset = (u64)-1; 804 805 path = btrfs_alloc_path(); 806 if (!path) 807 return -ENOMEM; 808 path->search_commit_root = !!search_commit_root; 809 810 /* 811 * grab both a lock on the path and a lock on the delayed ref head. 812 * We need both to get a consistent picture of how the refs look 813 * at a specified point in time 814 */ 815 again: 816 head = NULL; 817 818 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0); 819 if (ret < 0) 820 goto out; 821 BUG_ON(ret == 0); 822 823 if (trans != BTRFS_BACKREF_SEARCH_COMMIT_ROOT) { 824 /* 825 * look if there are updates for this ref queued and lock the 826 * head 827 */ 828 delayed_refs = &trans->transaction->delayed_refs; 829 spin_lock(&delayed_refs->lock); 830 head = btrfs_find_delayed_ref_head(trans, bytenr); 831 if (head) { 832 if (!mutex_trylock(&head->mutex)) { 833 atomic_inc(&head->node.refs); 834 spin_unlock(&delayed_refs->lock); 835 836 btrfs_release_path(path); 837 838 /* 839 * Mutex was contended, block until it's 840 * released and try again 841 */ 842 mutex_lock(&head->mutex); 843 mutex_unlock(&head->mutex); 844 btrfs_put_delayed_ref(&head->node); 845 goto again; 846 } 847 ret = __add_delayed_refs(head, time_seq, 848 &prefs_delayed); 849 mutex_unlock(&head->mutex); 850 if (ret) { 851 spin_unlock(&delayed_refs->lock); 852 goto out; 853 } 854 } 855 spin_unlock(&delayed_refs->lock); 856 } 857 858 if (path->slots[0]) { 859 struct extent_buffer *leaf; 860 int slot; 861 862 path->slots[0]--; 863 leaf = path->nodes[0]; 864 slot = path->slots[0]; 865 btrfs_item_key_to_cpu(leaf, &key, slot); 866 if (key.objectid == bytenr && 867 key.type == BTRFS_EXTENT_ITEM_KEY) { 868 ret = __add_inline_refs(fs_info, path, bytenr, 869 &info_level, &prefs); 870 if (ret) 871 goto out; 872 ret = __add_keyed_refs(fs_info, path, bytenr, 873 info_level, &prefs); 874 if (ret) 875 goto out; 876 } 877 } 878 btrfs_release_path(path); 879 880 list_splice_init(&prefs_delayed, &prefs); 881 882 ret = __add_missing_keys(fs_info, &prefs); 883 if (ret) 884 goto out; 885 886 ret = __merge_refs(&prefs, 1); 887 if (ret) 888 goto out; 889 890 ret = __resolve_indirect_refs(fs_info, search_commit_root, time_seq, 891 &prefs, extent_item_pos); 892 if (ret) 893 goto out; 894 895 ret = __merge_refs(&prefs, 2); 896 if (ret) 897 goto out; 898 899 while (!list_empty(&prefs)) { 900 ref = list_first_entry(&prefs, struct __prelim_ref, list); 901 list_del(&ref->list); 902 WARN_ON(ref->count < 0); 903 if (ref->count && ref->root_id && ref->parent == 0) { 904 /* no parent == root of tree */ 905 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS); 906 BUG_ON(ret < 0); 907 } 908 if (ref->count && ref->parent) { 909 struct extent_inode_elem *eie = NULL; 910 if (extent_item_pos && !ref->inode_list) { 911 u32 bsz; 912 struct extent_buffer *eb; 913 bsz = btrfs_level_size(fs_info->extent_root, 914 info_level); 915 eb = read_tree_block(fs_info->extent_root, 916 ref->parent, bsz, 0); 917 BUG_ON(!eb); 918 ret = find_extent_in_eb(eb, bytenr, 919 *extent_item_pos, &eie); 920 ref->inode_list = eie; 921 free_extent_buffer(eb); 922 } 923 ret = ulist_add_merge(refs, ref->parent, 924 (uintptr_t)ref->inode_list, 925 (u64 *)&eie, GFP_NOFS); 926 if (!ret && extent_item_pos) { 927 /* 928 * we've recorded that parent, so we must extend 929 * its inode list here 930 */ 931 BUG_ON(!eie); 932 while (eie->next) 933 eie = eie->next; 934 eie->next = ref->inode_list; 935 } 936 BUG_ON(ret < 0); 937 } 938 kfree(ref); 939 } 940 941 out: 942 btrfs_free_path(path); 943 while (!list_empty(&prefs)) { 944 ref = list_first_entry(&prefs, struct __prelim_ref, list); 945 list_del(&ref->list); 946 kfree(ref); 947 } 948 while (!list_empty(&prefs_delayed)) { 949 ref = list_first_entry(&prefs_delayed, struct __prelim_ref, 950 list); 951 list_del(&ref->list); 952 kfree(ref); 953 } 954 955 return ret; 956 } 957 958 static void free_leaf_list(struct ulist *blocks) 959 { 960 struct ulist_node *node = NULL; 961 struct extent_inode_elem *eie; 962 struct extent_inode_elem *eie_next; 963 struct ulist_iterator uiter; 964 965 ULIST_ITER_INIT(&uiter); 966 while ((node = ulist_next(blocks, &uiter))) { 967 if (!node->aux) 968 continue; 969 eie = (struct extent_inode_elem *)(uintptr_t)node->aux; 970 for (; eie; eie = eie_next) { 971 eie_next = eie->next; 972 kfree(eie); 973 } 974 node->aux = 0; 975 } 976 977 ulist_free(blocks); 978 } 979 980 /* 981 * Finds all leafs with a reference to the specified combination of bytenr and 982 * offset. key_list_head will point to a list of corresponding keys (caller must 983 * free each list element). The leafs will be stored in the leafs ulist, which 984 * must be freed with ulist_free. 985 * 986 * returns 0 on success, <0 on error 987 */ 988 static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, 989 struct btrfs_fs_info *fs_info, u64 bytenr, 990 u64 time_seq, struct ulist **leafs, 991 const u64 *extent_item_pos) 992 { 993 struct ulist *tmp; 994 int ret; 995 996 tmp = ulist_alloc(GFP_NOFS); 997 if (!tmp) 998 return -ENOMEM; 999 *leafs = ulist_alloc(GFP_NOFS); 1000 if (!*leafs) { 1001 ulist_free(tmp); 1002 return -ENOMEM; 1003 } 1004 1005 ret = find_parent_nodes(trans, fs_info, bytenr, 1006 time_seq, *leafs, tmp, extent_item_pos); 1007 ulist_free(tmp); 1008 1009 if (ret < 0 && ret != -ENOENT) { 1010 free_leaf_list(*leafs); 1011 return ret; 1012 } 1013 1014 return 0; 1015 } 1016 1017 /* 1018 * walk all backrefs for a given extent to find all roots that reference this 1019 * extent. Walking a backref means finding all extents that reference this 1020 * extent and in turn walk the backrefs of those, too. Naturally this is a 1021 * recursive process, but here it is implemented in an iterative fashion: We 1022 * find all referencing extents for the extent in question and put them on a 1023 * list. In turn, we find all referencing extents for those, further appending 1024 * to the list. The way we iterate the list allows adding more elements after 1025 * the current while iterating. The process stops when we reach the end of the 1026 * list. Found roots are added to the roots list. 1027 * 1028 * returns 0 on success, < 0 on error. 1029 */ 1030 int btrfs_find_all_roots(struct btrfs_trans_handle *trans, 1031 struct btrfs_fs_info *fs_info, u64 bytenr, 1032 u64 time_seq, struct ulist **roots) 1033 { 1034 struct ulist *tmp; 1035 struct ulist_node *node = NULL; 1036 struct ulist_iterator uiter; 1037 int ret; 1038 1039 tmp = ulist_alloc(GFP_NOFS); 1040 if (!tmp) 1041 return -ENOMEM; 1042 *roots = ulist_alloc(GFP_NOFS); 1043 if (!*roots) { 1044 ulist_free(tmp); 1045 return -ENOMEM; 1046 } 1047 1048 ULIST_ITER_INIT(&uiter); 1049 while (1) { 1050 ret = find_parent_nodes(trans, fs_info, bytenr, 1051 time_seq, tmp, *roots, NULL); 1052 if (ret < 0 && ret != -ENOENT) { 1053 ulist_free(tmp); 1054 ulist_free(*roots); 1055 return ret; 1056 } 1057 node = ulist_next(tmp, &uiter); 1058 if (!node) 1059 break; 1060 bytenr = node->val; 1061 } 1062 1063 ulist_free(tmp); 1064 return 0; 1065 } 1066 1067 1068 static int __inode_info(u64 inum, u64 ioff, u8 key_type, 1069 struct btrfs_root *fs_root, struct btrfs_path *path, 1070 struct btrfs_key *found_key) 1071 { 1072 int ret; 1073 struct btrfs_key key; 1074 struct extent_buffer *eb; 1075 1076 key.type = key_type; 1077 key.objectid = inum; 1078 key.offset = ioff; 1079 1080 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); 1081 if (ret < 0) 1082 return ret; 1083 1084 eb = path->nodes[0]; 1085 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { 1086 ret = btrfs_next_leaf(fs_root, path); 1087 if (ret) 1088 return ret; 1089 eb = path->nodes[0]; 1090 } 1091 1092 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); 1093 if (found_key->type != key.type || found_key->objectid != key.objectid) 1094 return 1; 1095 1096 return 0; 1097 } 1098 1099 /* 1100 * this makes the path point to (inum INODE_ITEM ioff) 1101 */ 1102 int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root, 1103 struct btrfs_path *path) 1104 { 1105 struct btrfs_key key; 1106 return __inode_info(inum, ioff, BTRFS_INODE_ITEM_KEY, fs_root, path, 1107 &key); 1108 } 1109 1110 static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root, 1111 struct btrfs_path *path, 1112 struct btrfs_key *found_key) 1113 { 1114 return __inode_info(inum, ioff, BTRFS_INODE_REF_KEY, fs_root, path, 1115 found_key); 1116 } 1117 1118 int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid, 1119 u64 start_off, struct btrfs_path *path, 1120 struct btrfs_inode_extref **ret_extref, 1121 u64 *found_off) 1122 { 1123 int ret, slot; 1124 struct btrfs_key key; 1125 struct btrfs_key found_key; 1126 struct btrfs_inode_extref *extref; 1127 struct extent_buffer *leaf; 1128 unsigned long ptr; 1129 1130 key.objectid = inode_objectid; 1131 btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY); 1132 key.offset = start_off; 1133 1134 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 1135 if (ret < 0) 1136 return ret; 1137 1138 while (1) { 1139 leaf = path->nodes[0]; 1140 slot = path->slots[0]; 1141 if (slot >= btrfs_header_nritems(leaf)) { 1142 /* 1143 * If the item at offset is not found, 1144 * btrfs_search_slot will point us to the slot 1145 * where it should be inserted. In our case 1146 * that will be the slot directly before the 1147 * next INODE_REF_KEY_V2 item. In the case 1148 * that we're pointing to the last slot in a 1149 * leaf, we must move one leaf over. 1150 */ 1151 ret = btrfs_next_leaf(root, path); 1152 if (ret) { 1153 if (ret >= 1) 1154 ret = -ENOENT; 1155 break; 1156 } 1157 continue; 1158 } 1159 1160 btrfs_item_key_to_cpu(leaf, &found_key, slot); 1161 1162 /* 1163 * Check that we're still looking at an extended ref key for 1164 * this particular objectid. If we have different 1165 * objectid or type then there are no more to be found 1166 * in the tree and we can exit. 1167 */ 1168 ret = -ENOENT; 1169 if (found_key.objectid != inode_objectid) 1170 break; 1171 if (btrfs_key_type(&found_key) != BTRFS_INODE_EXTREF_KEY) 1172 break; 1173 1174 ret = 0; 1175 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 1176 extref = (struct btrfs_inode_extref *)ptr; 1177 *ret_extref = extref; 1178 if (found_off) 1179 *found_off = found_key.offset; 1180 break; 1181 } 1182 1183 return ret; 1184 } 1185 1186 char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path, 1187 u32 name_len, unsigned long name_off, 1188 struct extent_buffer *eb_in, u64 parent, 1189 char *dest, u32 size) 1190 { 1191 int slot; 1192 u64 next_inum; 1193 int ret; 1194 s64 bytes_left = ((s64)size) - 1; 1195 struct extent_buffer *eb = eb_in; 1196 struct btrfs_key found_key; 1197 int leave_spinning = path->leave_spinning; 1198 struct btrfs_inode_ref *iref; 1199 1200 if (bytes_left >= 0) 1201 dest[bytes_left] = '\0'; 1202 1203 path->leave_spinning = 1; 1204 while (1) { 1205 bytes_left -= name_len; 1206 if (bytes_left >= 0) 1207 read_extent_buffer(eb, dest + bytes_left, 1208 name_off, name_len); 1209 if (eb != eb_in) { 1210 btrfs_tree_read_unlock_blocking(eb); 1211 free_extent_buffer(eb); 1212 } 1213 ret = inode_ref_info(parent, 0, fs_root, path, &found_key); 1214 if (ret > 0) 1215 ret = -ENOENT; 1216 if (ret) 1217 break; 1218 1219 next_inum = found_key.offset; 1220 1221 /* regular exit ahead */ 1222 if (parent == next_inum) 1223 break; 1224 1225 slot = path->slots[0]; 1226 eb = path->nodes[0]; 1227 /* make sure we can use eb after releasing the path */ 1228 if (eb != eb_in) { 1229 atomic_inc(&eb->refs); 1230 btrfs_tree_read_lock(eb); 1231 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK); 1232 } 1233 btrfs_release_path(path); 1234 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref); 1235 1236 name_len = btrfs_inode_ref_name_len(eb, iref); 1237 name_off = (unsigned long)(iref + 1); 1238 1239 parent = next_inum; 1240 --bytes_left; 1241 if (bytes_left >= 0) 1242 dest[bytes_left] = '/'; 1243 } 1244 1245 btrfs_release_path(path); 1246 path->leave_spinning = leave_spinning; 1247 1248 if (ret) 1249 return ERR_PTR(ret); 1250 1251 return dest + bytes_left; 1252 } 1253 1254 /* 1255 * this iterates to turn a btrfs_inode_ref into a full filesystem path. elements 1256 * of the path are separated by '/' and the path is guaranteed to be 1257 * 0-terminated. the path is only given within the current file system. 1258 * Therefore, it never starts with a '/'. the caller is responsible to provide 1259 * "size" bytes in "dest". the dest buffer will be filled backwards. finally, 1260 * the start point of the resulting string is returned. this pointer is within 1261 * dest, normally. 1262 * in case the path buffer would overflow, the pointer is decremented further 1263 * as if output was written to the buffer, though no more output is actually 1264 * generated. that way, the caller can determine how much space would be 1265 * required for the path to fit into the buffer. in that case, the returned 1266 * value will be smaller than dest. callers must check this! 1267 */ 1268 char *btrfs_iref_to_path(struct btrfs_root *fs_root, 1269 struct btrfs_path *path, 1270 struct btrfs_inode_ref *iref, 1271 struct extent_buffer *eb_in, u64 parent, 1272 char *dest, u32 size) 1273 { 1274 return btrfs_ref_to_path(fs_root, path, 1275 btrfs_inode_ref_name_len(eb_in, iref), 1276 (unsigned long)(iref + 1), 1277 eb_in, parent, dest, size); 1278 } 1279 1280 /* 1281 * this makes the path point to (logical EXTENT_ITEM *) 1282 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for 1283 * tree blocks and <0 on error. 1284 */ 1285 int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, 1286 struct btrfs_path *path, struct btrfs_key *found_key, 1287 u64 *flags_ret) 1288 { 1289 int ret; 1290 u64 flags; 1291 u32 item_size; 1292 struct extent_buffer *eb; 1293 struct btrfs_extent_item *ei; 1294 struct btrfs_key key; 1295 1296 key.type = BTRFS_EXTENT_ITEM_KEY; 1297 key.objectid = logical; 1298 key.offset = (u64)-1; 1299 1300 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0); 1301 if (ret < 0) 1302 return ret; 1303 ret = btrfs_previous_item(fs_info->extent_root, path, 1304 0, BTRFS_EXTENT_ITEM_KEY); 1305 if (ret < 0) 1306 return ret; 1307 1308 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]); 1309 if (found_key->type != BTRFS_EXTENT_ITEM_KEY || 1310 found_key->objectid > logical || 1311 found_key->objectid + found_key->offset <= logical) { 1312 pr_debug("logical %llu is not within any extent\n", 1313 (unsigned long long)logical); 1314 return -ENOENT; 1315 } 1316 1317 eb = path->nodes[0]; 1318 item_size = btrfs_item_size_nr(eb, path->slots[0]); 1319 BUG_ON(item_size < sizeof(*ei)); 1320 1321 ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item); 1322 flags = btrfs_extent_flags(eb, ei); 1323 1324 pr_debug("logical %llu is at position %llu within the extent (%llu " 1325 "EXTENT_ITEM %llu) flags %#llx size %u\n", 1326 (unsigned long long)logical, 1327 (unsigned long long)(logical - found_key->objectid), 1328 (unsigned long long)found_key->objectid, 1329 (unsigned long long)found_key->offset, 1330 (unsigned long long)flags, item_size); 1331 1332 WARN_ON(!flags_ret); 1333 if (flags_ret) { 1334 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) 1335 *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK; 1336 else if (flags & BTRFS_EXTENT_FLAG_DATA) 1337 *flags_ret = BTRFS_EXTENT_FLAG_DATA; 1338 else 1339 BUG_ON(1); 1340 return 0; 1341 } 1342 1343 return -EIO; 1344 } 1345 1346 /* 1347 * helper function to iterate extent inline refs. ptr must point to a 0 value 1348 * for the first call and may be modified. it is used to track state. 1349 * if more refs exist, 0 is returned and the next call to 1350 * __get_extent_inline_ref must pass the modified ptr parameter to get the 1351 * next ref. after the last ref was processed, 1 is returned. 1352 * returns <0 on error 1353 */ 1354 static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb, 1355 struct btrfs_extent_item *ei, u32 item_size, 1356 struct btrfs_extent_inline_ref **out_eiref, 1357 int *out_type) 1358 { 1359 unsigned long end; 1360 u64 flags; 1361 struct btrfs_tree_block_info *info; 1362 1363 if (!*ptr) { 1364 /* first call */ 1365 flags = btrfs_extent_flags(eb, ei); 1366 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { 1367 info = (struct btrfs_tree_block_info *)(ei + 1); 1368 *out_eiref = 1369 (struct btrfs_extent_inline_ref *)(info + 1); 1370 } else { 1371 *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1); 1372 } 1373 *ptr = (unsigned long)*out_eiref; 1374 if ((void *)*ptr >= (void *)ei + item_size) 1375 return -ENOENT; 1376 } 1377 1378 end = (unsigned long)ei + item_size; 1379 *out_eiref = (struct btrfs_extent_inline_ref *)*ptr; 1380 *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref); 1381 1382 *ptr += btrfs_extent_inline_ref_size(*out_type); 1383 WARN_ON(*ptr > end); 1384 if (*ptr == end) 1385 return 1; /* last */ 1386 1387 return 0; 1388 } 1389 1390 /* 1391 * reads the tree block backref for an extent. tree level and root are returned 1392 * through out_level and out_root. ptr must point to a 0 value for the first 1393 * call and may be modified (see __get_extent_inline_ref comment). 1394 * returns 0 if data was provided, 1 if there was no more data to provide or 1395 * <0 on error. 1396 */ 1397 int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb, 1398 struct btrfs_extent_item *ei, u32 item_size, 1399 u64 *out_root, u8 *out_level) 1400 { 1401 int ret; 1402 int type; 1403 struct btrfs_tree_block_info *info; 1404 struct btrfs_extent_inline_ref *eiref; 1405 1406 if (*ptr == (unsigned long)-1) 1407 return 1; 1408 1409 while (1) { 1410 ret = __get_extent_inline_ref(ptr, eb, ei, item_size, 1411 &eiref, &type); 1412 if (ret < 0) 1413 return ret; 1414 1415 if (type == BTRFS_TREE_BLOCK_REF_KEY || 1416 type == BTRFS_SHARED_BLOCK_REF_KEY) 1417 break; 1418 1419 if (ret == 1) 1420 return 1; 1421 } 1422 1423 /* we can treat both ref types equally here */ 1424 info = (struct btrfs_tree_block_info *)(ei + 1); 1425 *out_root = btrfs_extent_inline_ref_offset(eb, eiref); 1426 *out_level = btrfs_tree_block_level(eb, info); 1427 1428 if (ret == 1) 1429 *ptr = (unsigned long)-1; 1430 1431 return 0; 1432 } 1433 1434 static int iterate_leaf_refs(struct extent_inode_elem *inode_list, 1435 u64 root, u64 extent_item_objectid, 1436 iterate_extent_inodes_t *iterate, void *ctx) 1437 { 1438 struct extent_inode_elem *eie; 1439 int ret = 0; 1440 1441 for (eie = inode_list; eie; eie = eie->next) { 1442 pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), " 1443 "root %llu\n", extent_item_objectid, 1444 eie->inum, eie->offset, root); 1445 ret = iterate(eie->inum, eie->offset, root, ctx); 1446 if (ret) { 1447 pr_debug("stopping iteration for %llu due to ret=%d\n", 1448 extent_item_objectid, ret); 1449 break; 1450 } 1451 } 1452 1453 return ret; 1454 } 1455 1456 /* 1457 * calls iterate() for every inode that references the extent identified by 1458 * the given parameters. 1459 * when the iterator function returns a non-zero value, iteration stops. 1460 */ 1461 int iterate_extent_inodes(struct btrfs_fs_info *fs_info, 1462 u64 extent_item_objectid, u64 extent_item_pos, 1463 int search_commit_root, 1464 iterate_extent_inodes_t *iterate, void *ctx) 1465 { 1466 int ret; 1467 struct list_head data_refs = LIST_HEAD_INIT(data_refs); 1468 struct list_head shared_refs = LIST_HEAD_INIT(shared_refs); 1469 struct btrfs_trans_handle *trans; 1470 struct ulist *refs = NULL; 1471 struct ulist *roots = NULL; 1472 struct ulist_node *ref_node = NULL; 1473 struct ulist_node *root_node = NULL; 1474 struct seq_list tree_mod_seq_elem = {}; 1475 struct ulist_iterator ref_uiter; 1476 struct ulist_iterator root_uiter; 1477 1478 pr_debug("resolving all inodes for extent %llu\n", 1479 extent_item_objectid); 1480 1481 if (search_commit_root) { 1482 trans = BTRFS_BACKREF_SEARCH_COMMIT_ROOT; 1483 } else { 1484 trans = btrfs_join_transaction(fs_info->extent_root); 1485 if (IS_ERR(trans)) 1486 return PTR_ERR(trans); 1487 btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem); 1488 } 1489 1490 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid, 1491 tree_mod_seq_elem.seq, &refs, 1492 &extent_item_pos); 1493 if (ret) 1494 goto out; 1495 1496 ULIST_ITER_INIT(&ref_uiter); 1497 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) { 1498 ret = btrfs_find_all_roots(trans, fs_info, ref_node->val, 1499 tree_mod_seq_elem.seq, &roots); 1500 if (ret) 1501 break; 1502 ULIST_ITER_INIT(&root_uiter); 1503 while (!ret && (root_node = ulist_next(roots, &root_uiter))) { 1504 pr_debug("root %llu references leaf %llu, data list " 1505 "%#llx\n", root_node->val, ref_node->val, 1506 (long long)ref_node->aux); 1507 ret = iterate_leaf_refs((struct extent_inode_elem *) 1508 (uintptr_t)ref_node->aux, 1509 root_node->val, 1510 extent_item_objectid, 1511 iterate, ctx); 1512 } 1513 ulist_free(roots); 1514 roots = NULL; 1515 } 1516 1517 free_leaf_list(refs); 1518 ulist_free(roots); 1519 out: 1520 if (!search_commit_root) { 1521 btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem); 1522 btrfs_end_transaction(trans, fs_info->extent_root); 1523 } 1524 1525 return ret; 1526 } 1527 1528 int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, 1529 struct btrfs_path *path, 1530 iterate_extent_inodes_t *iterate, void *ctx) 1531 { 1532 int ret; 1533 u64 extent_item_pos; 1534 u64 flags = 0; 1535 struct btrfs_key found_key; 1536 int search_commit_root = path->search_commit_root; 1537 1538 ret = extent_from_logical(fs_info, logical, path, &found_key, &flags); 1539 btrfs_release_path(path); 1540 if (ret < 0) 1541 return ret; 1542 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) 1543 return -EINVAL; 1544 1545 extent_item_pos = logical - found_key.objectid; 1546 ret = iterate_extent_inodes(fs_info, found_key.objectid, 1547 extent_item_pos, search_commit_root, 1548 iterate, ctx); 1549 1550 return ret; 1551 } 1552 1553 typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off, 1554 struct extent_buffer *eb, void *ctx); 1555 1556 static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root, 1557 struct btrfs_path *path, 1558 iterate_irefs_t *iterate, void *ctx) 1559 { 1560 int ret = 0; 1561 int slot; 1562 u32 cur; 1563 u32 len; 1564 u32 name_len; 1565 u64 parent = 0; 1566 int found = 0; 1567 struct extent_buffer *eb; 1568 struct btrfs_item *item; 1569 struct btrfs_inode_ref *iref; 1570 struct btrfs_key found_key; 1571 1572 while (!ret) { 1573 path->leave_spinning = 1; 1574 ret = inode_ref_info(inum, parent ? parent+1 : 0, fs_root, path, 1575 &found_key); 1576 if (ret < 0) 1577 break; 1578 if (ret) { 1579 ret = found ? 0 : -ENOENT; 1580 break; 1581 } 1582 ++found; 1583 1584 parent = found_key.offset; 1585 slot = path->slots[0]; 1586 eb = path->nodes[0]; 1587 /* make sure we can use eb after releasing the path */ 1588 atomic_inc(&eb->refs); 1589 btrfs_tree_read_lock(eb); 1590 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK); 1591 btrfs_release_path(path); 1592 1593 item = btrfs_item_nr(eb, slot); 1594 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref); 1595 1596 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) { 1597 name_len = btrfs_inode_ref_name_len(eb, iref); 1598 /* path must be released before calling iterate()! */ 1599 pr_debug("following ref at offset %u for inode %llu in " 1600 "tree %llu\n", cur, 1601 (unsigned long long)found_key.objectid, 1602 (unsigned long long)fs_root->objectid); 1603 ret = iterate(parent, name_len, 1604 (unsigned long)(iref + 1), eb, ctx); 1605 if (ret) 1606 break; 1607 len = sizeof(*iref) + name_len; 1608 iref = (struct btrfs_inode_ref *)((char *)iref + len); 1609 } 1610 btrfs_tree_read_unlock_blocking(eb); 1611 free_extent_buffer(eb); 1612 } 1613 1614 btrfs_release_path(path); 1615 1616 return ret; 1617 } 1618 1619 static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root, 1620 struct btrfs_path *path, 1621 iterate_irefs_t *iterate, void *ctx) 1622 { 1623 int ret; 1624 int slot; 1625 u64 offset = 0; 1626 u64 parent; 1627 int found = 0; 1628 struct extent_buffer *eb; 1629 struct btrfs_inode_extref *extref; 1630 struct extent_buffer *leaf; 1631 u32 item_size; 1632 u32 cur_offset; 1633 unsigned long ptr; 1634 1635 while (1) { 1636 ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref, 1637 &offset); 1638 if (ret < 0) 1639 break; 1640 if (ret) { 1641 ret = found ? 0 : -ENOENT; 1642 break; 1643 } 1644 ++found; 1645 1646 slot = path->slots[0]; 1647 eb = path->nodes[0]; 1648 /* make sure we can use eb after releasing the path */ 1649 atomic_inc(&eb->refs); 1650 1651 btrfs_tree_read_lock(eb); 1652 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK); 1653 btrfs_release_path(path); 1654 1655 leaf = path->nodes[0]; 1656 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 1657 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 1658 cur_offset = 0; 1659 1660 while (cur_offset < item_size) { 1661 u32 name_len; 1662 1663 extref = (struct btrfs_inode_extref *)(ptr + cur_offset); 1664 parent = btrfs_inode_extref_parent(eb, extref); 1665 name_len = btrfs_inode_extref_name_len(eb, extref); 1666 ret = iterate(parent, name_len, 1667 (unsigned long)&extref->name, eb, ctx); 1668 if (ret) 1669 break; 1670 1671 cur_offset += btrfs_inode_extref_name_len(leaf, extref); 1672 cur_offset += sizeof(*extref); 1673 } 1674 btrfs_tree_read_unlock_blocking(eb); 1675 free_extent_buffer(eb); 1676 1677 offset++; 1678 } 1679 1680 btrfs_release_path(path); 1681 1682 return ret; 1683 } 1684 1685 static int iterate_irefs(u64 inum, struct btrfs_root *fs_root, 1686 struct btrfs_path *path, iterate_irefs_t *iterate, 1687 void *ctx) 1688 { 1689 int ret; 1690 int found_refs = 0; 1691 1692 ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx); 1693 if (!ret) 1694 ++found_refs; 1695 else if (ret != -ENOENT) 1696 return ret; 1697 1698 ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx); 1699 if (ret == -ENOENT && found_refs) 1700 return 0; 1701 1702 return ret; 1703 } 1704 1705 /* 1706 * returns 0 if the path could be dumped (probably truncated) 1707 * returns <0 in case of an error 1708 */ 1709 static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off, 1710 struct extent_buffer *eb, void *ctx) 1711 { 1712 struct inode_fs_paths *ipath = ctx; 1713 char *fspath; 1714 char *fspath_min; 1715 int i = ipath->fspath->elem_cnt; 1716 const int s_ptr = sizeof(char *); 1717 u32 bytes_left; 1718 1719 bytes_left = ipath->fspath->bytes_left > s_ptr ? 1720 ipath->fspath->bytes_left - s_ptr : 0; 1721 1722 fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr; 1723 fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len, 1724 name_off, eb, inum, fspath_min, bytes_left); 1725 if (IS_ERR(fspath)) 1726 return PTR_ERR(fspath); 1727 1728 if (fspath > fspath_min) { 1729 ipath->fspath->val[i] = (u64)(unsigned long)fspath; 1730 ++ipath->fspath->elem_cnt; 1731 ipath->fspath->bytes_left = fspath - fspath_min; 1732 } else { 1733 ++ipath->fspath->elem_missed; 1734 ipath->fspath->bytes_missing += fspath_min - fspath; 1735 ipath->fspath->bytes_left = 0; 1736 } 1737 1738 return 0; 1739 } 1740 1741 /* 1742 * this dumps all file system paths to the inode into the ipath struct, provided 1743 * is has been created large enough. each path is zero-terminated and accessed 1744 * from ipath->fspath->val[i]. 1745 * when it returns, there are ipath->fspath->elem_cnt number of paths available 1746 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the 1747 * number of missed paths in recored in ipath->fspath->elem_missed, otherwise, 1748 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would 1749 * have been needed to return all paths. 1750 */ 1751 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath) 1752 { 1753 return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path, 1754 inode_to_path, ipath); 1755 } 1756 1757 struct btrfs_data_container *init_data_container(u32 total_bytes) 1758 { 1759 struct btrfs_data_container *data; 1760 size_t alloc_bytes; 1761 1762 alloc_bytes = max_t(size_t, total_bytes, sizeof(*data)); 1763 data = vmalloc(alloc_bytes); 1764 if (!data) 1765 return ERR_PTR(-ENOMEM); 1766 1767 if (total_bytes >= sizeof(*data)) { 1768 data->bytes_left = total_bytes - sizeof(*data); 1769 data->bytes_missing = 0; 1770 } else { 1771 data->bytes_missing = sizeof(*data) - total_bytes; 1772 data->bytes_left = 0; 1773 } 1774 1775 data->elem_cnt = 0; 1776 data->elem_missed = 0; 1777 1778 return data; 1779 } 1780 1781 /* 1782 * allocates space to return multiple file system paths for an inode. 1783 * total_bytes to allocate are passed, note that space usable for actual path 1784 * information will be total_bytes - sizeof(struct inode_fs_paths). 1785 * the returned pointer must be freed with free_ipath() in the end. 1786 */ 1787 struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root, 1788 struct btrfs_path *path) 1789 { 1790 struct inode_fs_paths *ifp; 1791 struct btrfs_data_container *fspath; 1792 1793 fspath = init_data_container(total_bytes); 1794 if (IS_ERR(fspath)) 1795 return (void *)fspath; 1796 1797 ifp = kmalloc(sizeof(*ifp), GFP_NOFS); 1798 if (!ifp) { 1799 kfree(fspath); 1800 return ERR_PTR(-ENOMEM); 1801 } 1802 1803 ifp->btrfs_path = path; 1804 ifp->fspath = fspath; 1805 ifp->fs_root = fs_root; 1806 1807 return ifp; 1808 } 1809 1810 void free_ipath(struct inode_fs_paths *ipath) 1811 { 1812 if (!ipath) 1813 return; 1814 vfree(ipath->fspath); 1815 kfree(ipath); 1816 } 1817