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