fs/btrfs/backref.c

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