fs/btrfs/backref.c

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