fs/btrfs/backref.c

   1 /*
   2  * Copyright (C) 2011 STRATO.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include "ctree.h"
  20 #include "disk-io.h"
  21 #include "backref.h"
  22
  23 struct __data_ref {
  24         struct list_head list;
  25         u64 inum;
  26         u64 root;
  27         u64 extent_data_item_offset;
  28 };
  29
  30 struct __shared_ref {
  31         struct list_head list;
  32         u64 disk_byte;
  33 };
  34
  35 static int __inode_info(u64 inum, u64 ioff, u8 key_type,
  36                         struct btrfs_root *fs_root, struct btrfs_path *path,
  37                         struct btrfs_key *found_key)
  38 {
  39         int ret;
  40         struct btrfs_key key;
  41         struct extent_buffer *eb;
  42
  43         key.type = key_type;
  44         key.objectid = inum;
  45         key.offset = ioff;
  46
  47         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
  48         if (ret < 0)
  49                 return ret;
  50
  51         eb = path->nodes[0];
  52         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
  53                 ret = btrfs_next_leaf(fs_root, path);
  54                 if (ret)
  55                         return ret;
  56                 eb = path->nodes[0];
  57         }
  58
  59         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
  60         if (found_key->type != key.type || found_key->objectid != key.objectid)
  61                 return 1;
  62
  63         return 0;
  64 }
  65
  66 /*
  67  * this makes the path point to (inum INODE_ITEM ioff)
  68  */
  69 int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
  70                         struct btrfs_path *path)
  71 {
  72         struct btrfs_key key;
  73         return __inode_info(inum, ioff, BTRFS_INODE_ITEM_KEY, fs_root, path,
  74                                 &key);
  75 }
  76
  77 static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
  78                                 struct btrfs_path *path,
  79                                 struct btrfs_key *found_key)
  80 {
  81         return __inode_info(inum, ioff, BTRFS_INODE_REF_KEY, fs_root, path,
  82                                 found_key);
  83 }
  84
  85 /*
  86  * this iterates to turn a btrfs_inode_ref into a full filesystem path. elements
  87  * of the path are separated by '/' and the path is guaranteed to be
  88  * 0-terminated. the path is only given within the current file system.
  89  * Therefore, it never starts with a '/'. the caller is responsible to provide
  90  * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
  91  * the start point of the resulting string is returned. this pointer is within
  92  * dest, normally.
  93  * in case the path buffer would overflow, the pointer is decremented further
  94  * as if output was written to the buffer, though no more output is actually
  95  * generated. that way, the caller can determine how much space would be
  96  * required for the path to fit into the buffer. in that case, the returned
  97  * value will be smaller than dest. callers must check this!
  98  */
  99 static char *iref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
 100                                 struct btrfs_inode_ref *iref,
 101                                 struct extent_buffer *eb_in, u64 parent,
 102                                 char *dest, u32 size)
 103 {
 104         u32 len;
 105         int slot;
 106         u64 next_inum;
 107         int ret;
 108         s64 bytes_left = size - 1;
 109         struct extent_buffer *eb = eb_in;
 110         struct btrfs_key found_key;
 111
 112         if (bytes_left >= 0)
 113                 dest[bytes_left] = '\0';
 114
 115         while (1) {
 116                 len = btrfs_inode_ref_name_len(eb, iref);
 117                 bytes_left -= len;
 118                 if (bytes_left >= 0)
 119                         read_extent_buffer(eb, dest + bytes_left,
 120                                                 (unsigned long)(iref + 1), len);
 121                 if (eb != eb_in)
 122                         free_extent_buffer(eb);
 123                 ret = inode_ref_info(parent, 0, fs_root, path, &found_key);
 124                 if (ret)
 125                         break;
 126                 next_inum = found_key.offset;
 127
 128                 /* regular exit ahead */
 129                 if (parent == next_inum)
 130                         break;
 131
 132                 slot = path->slots[0];
 133                 eb = path->nodes[0];
 134                 /* make sure we can use eb after releasing the path */
 135                 if (eb != eb_in)
 136                         atomic_inc(&eb->refs);
 137                 btrfs_release_path(path);
 138
 139                 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 140                 parent = next_inum;
 141                 --bytes_left;
 142                 if (bytes_left >= 0)
 143                         dest[bytes_left] = '/';
 144         }
 145
 146         btrfs_release_path(path);
 147
 148         if (ret)
 149                 return ERR_PTR(ret);
 150
 151         return dest + bytes_left;
 152 }
 153
 154 /*
 155  * this makes the path point to (logical EXTENT_ITEM *)
 156  * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
 157  * tree blocks and <0 on error.
 158  */
 159 int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
 160                         struct btrfs_path *path, struct btrfs_key *found_key)
 161 {
 162         int ret;
 163         u64 flags;
 164         u32 item_size;
 165         struct extent_buffer *eb;
 166         struct btrfs_extent_item *ei;
 167         struct btrfs_key key;
 168
 169         key.type = BTRFS_EXTENT_ITEM_KEY;
 170         key.objectid = logical;
 171         key.offset = (u64)-1;
 172
 173         ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
 174         if (ret < 0)
 175                 return ret;
 176         ret = btrfs_previous_item(fs_info->extent_root, path,
 177                                         0, BTRFS_EXTENT_ITEM_KEY);
 178         if (ret < 0)
 179                 return ret;
 180
 181         btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
 182         if (found_key->type != BTRFS_EXTENT_ITEM_KEY ||
 183             found_key->objectid > logical ||
 184             found_key->objectid + found_key->offset <= logical)
 185                 return -ENOENT;
 186
 187         eb = path->nodes[0];
 188         item_size = btrfs_item_size_nr(eb, path->slots[0]);
 189         BUG_ON(item_size < sizeof(*ei));
 190
 191         ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
 192         flags = btrfs_extent_flags(eb, ei);
 193
 194         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
 195                 return BTRFS_EXTENT_FLAG_TREE_BLOCK;
 196         if (flags & BTRFS_EXTENT_FLAG_DATA)
 197                 return BTRFS_EXTENT_FLAG_DATA;
 198
 199         return -EIO;
 200 }
 201
 202 /*
 203  * helper function to iterate extent inline refs. ptr must point to a 0 value
 204  * for the first call and may be modified. it is used to track state.
 205  * if more refs exist, 0 is returned and the next call to
 206  * __get_extent_inline_ref must pass the modified ptr parameter to get the
 207  * next ref. after the last ref was processed, 1 is returned.
 208  * returns <0 on error
 209  */
 210 static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
 211                                 struct btrfs_extent_item *ei, u32 item_size,
 212                                 struct btrfs_extent_inline_ref **out_eiref,
 213                                 int *out_type)
 214 {
 215         unsigned long end;
 216         u64 flags;
 217         struct btrfs_tree_block_info *info;
 218
 219         if (!*ptr) {
 220                 /* first call */
 221                 flags = btrfs_extent_flags(eb, ei);
 222                 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
 223                         info = (struct btrfs_tree_block_info *)(ei + 1);
 224                         *out_eiref =
 225                                 (struct btrfs_extent_inline_ref *)(info + 1);
 226                 } else {
 227                         *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
 228                 }
 229                 *ptr = (unsigned long)*out_eiref;
 230                 if ((void *)*ptr >= (void *)ei + item_size)
 231                         return -ENOENT;
 232         }
 233
 234         end = (unsigned long)ei + item_size;
 235         *out_eiref = (struct btrfs_extent_inline_ref *)*ptr;
 236         *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);
 237
 238         *ptr += btrfs_extent_inline_ref_size(*out_type);
 239         WARN_ON(*ptr > end);
 240         if (*ptr == end)
 241                 return 1; /* last */
 242
 243         return 0;
 244 }
 245
 246 /*
 247  * reads the tree block backref for an extent. tree level and root are returned
 248  * through out_level and out_root. ptr must point to a 0 value for the first
 249  * call and may be modified (see __get_extent_inline_ref comment).
 250  * returns 0 if data was provided, 1 if there was no more data to provide or
 251  * <0 on error.
 252  */
 253 int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
 254                                 struct btrfs_extent_item *ei, u32 item_size,
 255                                 u64 *out_root, u8 *out_level)
 256 {
 257         int ret;
 258         int type;
 259         struct btrfs_tree_block_info *info;
 260         struct btrfs_extent_inline_ref *eiref;
 261
 262         if (*ptr == (unsigned long)-1)
 263                 return 1;
 264
 265         while (1) {
 266                 ret = __get_extent_inline_ref(ptr, eb, ei, item_size,
 267                                                 &eiref, &type);
 268                 if (ret < 0)
 269                         return ret;
 270
 271                 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
 272                     type == BTRFS_SHARED_BLOCK_REF_KEY)
 273                         break;
 274
 275                 if (ret == 1)
 276                         return 1;
 277         }
 278
 279         /* we can treat both ref types equally here */
 280         info = (struct btrfs_tree_block_info *)(ei + 1);
 281         *out_root = btrfs_extent_inline_ref_offset(eb, eiref);
 282         *out_level = btrfs_tree_block_level(eb, info);
 283
 284         if (ret == 1)
 285                 *ptr = (unsigned long)-1;
 286
 287         return 0;
 288 }
 289
 290 static int __data_list_add(struct list_head *head, u64 inum,
 291                                 u64 extent_data_item_offset, u64 root)
 292 {
 293         struct __data_ref *ref;
 294
 295         ref = kmalloc(sizeof(*ref), GFP_NOFS);
 296         if (!ref)
 297                 return -ENOMEM;
 298
 299         ref->inum = inum;
 300         ref->extent_data_item_offset = extent_data_item_offset;
 301         ref->root = root;
 302         list_add_tail(&ref->list, head);
 303
 304         return 0;
 305 }
 306
 307 static int __data_list_add_eb(struct list_head *head, struct extent_buffer *eb,
 308                                 struct btrfs_extent_data_ref *dref)
 309 {
 310         return __data_list_add(head, btrfs_extent_data_ref_objectid(eb, dref),
 311                                 btrfs_extent_data_ref_offset(eb, dref),
 312                                 btrfs_extent_data_ref_root(eb, dref));
 313 }
 314
 315 static int __shared_list_add(struct list_head *head, u64 disk_byte)
 316 {
 317         struct __shared_ref *ref;
 318
 319         ref = kmalloc(sizeof(*ref), GFP_NOFS);
 320         if (!ref)
 321                 return -ENOMEM;
 322
 323         ref->disk_byte = disk_byte;
 324         list_add_tail(&ref->list, head);
 325
 326         return 0;
 327 }
 328
 329 static int __iter_shared_inline_ref_inodes(struct btrfs_fs_info *fs_info,
 330                                            u64 logical, u64 inum,
 331                                            u64 extent_data_item_offset,
 332                                            u64 extent_offset,
 333                                            struct btrfs_path *path,
 334                                            struct list_head *data_refs,
 335                                            iterate_extent_inodes_t *iterate,
 336                                            void *ctx)
 337 {
 338         u64 ref_root;
 339         u32 item_size;
 340         struct btrfs_key key;
 341         struct extent_buffer *eb;
 342         struct btrfs_extent_item *ei;
 343         struct btrfs_extent_inline_ref *eiref;
 344         struct __data_ref *ref;
 345         int ret;
 346         int type;
 347         int last;
 348         unsigned long ptr = 0;
 349
 350         WARN_ON(!list_empty(data_refs));
 351         ret = extent_from_logical(fs_info, logical, path, &key);
 352         if (ret & BTRFS_EXTENT_FLAG_DATA)
 353                 ret = -EIO;
 354         if (ret < 0)
 355                 goto out;
 356
 357         eb = path->nodes[0];
 358         ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
 359         item_size = btrfs_item_size_nr(eb, path->slots[0]);
 360
 361         ret = 0;
 362         ref_root = 0;
 363         /*
 364          * as done in iterate_extent_inodes, we first build a list of refs to
 365          * iterate, then free the path and then iterate them to avoid deadlocks.
 366          */
 367         do {
 368                 last = __get_extent_inline_ref(&ptr, eb, ei, item_size,
 369                                                 &eiref, &type);
 370                 if (last < 0) {
 371                         ret = last;
 372                         goto out;
 373                 }
 374                 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
 375                     type == BTRFS_SHARED_BLOCK_REF_KEY) {
 376                         ref_root = btrfs_extent_inline_ref_offset(eb, eiref);
 377                         ret = __data_list_add(data_refs, inum,
 378                                                 extent_data_item_offset,
 379                                                 ref_root);
 380                 }
 381         } while (!ret && !last);
 382
 383         btrfs_release_path(path);
 384
 385         if (ref_root == 0) {
 386                 printk(KERN_ERR "btrfs: failed to find tree block ref "
 387                         "for shared data backref %llu\n", logical);
 388                 WARN_ON(1);
 389                 ret = -EIO;
 390         }
 391
 392 out:
 393         while (!list_empty(data_refs)) {
 394                 ref = list_first_entry(data_refs, struct __data_ref, list);
 395                 list_del(&ref->list);
 396                 if (!ret)
 397                         ret = iterate(ref->inum, extent_offset +
 398                                         ref->extent_data_item_offset,
 399                                         ref->root, ctx);
 400                 kfree(ref);
 401         }
 402
 403         return ret;
 404 }
 405
 406 static int __iter_shared_inline_ref(struct btrfs_fs_info *fs_info,
 407                                     u64 logical, u64 orig_extent_item_objectid,
 408                                     u64 extent_offset, struct btrfs_path *path,
 409                                     struct list_head *data_refs,
 410                                     iterate_extent_inodes_t *iterate,
 411                                     void *ctx)
 412 {
 413         u64 disk_byte;
 414         struct btrfs_key key;
 415         struct btrfs_file_extent_item *fi;
 416         struct extent_buffer *eb;
 417         int slot;
 418         int nritems;
 419         int ret;
 420         int found = 0;
 421
 422         eb = read_tree_block(fs_info->tree_root, logical,
 423                                 fs_info->tree_root->leafsize, 0);
 424         if (!eb)
 425                 return -EIO;
 426
 427         /*
 428          * from the shared data ref, we only have the leaf but we need
 429          * the key. thus, we must look into all items and see that we
 430          * find one (some) with a reference to our extent item.
 431          */
 432         nritems = btrfs_header_nritems(eb);
 433         for (slot = 0; slot < nritems; ++slot) {
 434                 btrfs_item_key_to_cpu(eb, &key, slot);
 435                 if (key.type != BTRFS_EXTENT_DATA_KEY)
 436                         continue;
 437                 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 438                 if (!fi) {
 439                         free_extent_buffer(eb);
 440                         return -EIO;
 441                 }
 442                 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
 443                 if (disk_byte != orig_extent_item_objectid) {
 444                         if (found)
 445                                 break;
 446                         else
 447                                 continue;
 448                 }
 449                 ++found;
 450                 ret = __iter_shared_inline_ref_inodes(fs_info, logical,
 451                                                         key.objectid,
 452                                                         key.offset,
 453                                                         extent_offset, path,
 454                                                         data_refs,
 455                                                         iterate, ctx);
 456                 if (ret)
 457                         break;
 458         }
 459
 460         if (!found) {
 461                 printk(KERN_ERR "btrfs: failed to follow shared data backref "
 462                         "to parent %llu\n", logical);
 463                 WARN_ON(1);
 464                 ret = -EIO;
 465         }
 466
 467         free_extent_buffer(eb);
 468         return ret;
 469 }
 470
 471 /*
 472  * calls iterate() for every inode that references the extent identified by
 473  * the given parameters. will use the path given as a parameter and return it
 474  * released.
 475  * when the iterator function returns a non-zero value, iteration stops.
 476  */
 477 int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
 478                                 struct btrfs_path *path,
 479                                 u64 extent_item_objectid,
 480                                 u64 extent_offset,
 481                                 iterate_extent_inodes_t *iterate, void *ctx)
 482 {
 483         unsigned long ptr = 0;
 484         int last;
 485         int ret;
 486         int type;
 487         u64 logical;
 488         u32 item_size;
 489         struct btrfs_extent_inline_ref *eiref;
 490         struct btrfs_extent_data_ref *dref;
 491         struct extent_buffer *eb;
 492         struct btrfs_extent_item *ei;
 493         struct btrfs_key key;
 494         struct list_head data_refs = LIST_HEAD_INIT(data_refs);
 495         struct list_head shared_refs = LIST_HEAD_INIT(shared_refs);
 496         struct __data_ref *ref_d;
 497         struct __shared_ref *ref_s;
 498
 499         eb = path->nodes[0];
 500         ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
 501         item_size = btrfs_item_size_nr(eb, path->slots[0]);
 502
 503         /* first we iterate the inline refs, ... */
 504         do {
 505                 last = __get_extent_inline_ref(&ptr, eb, ei, item_size,
 506                                                 &eiref, &type);
 507                 if (last == -ENOENT) {
 508                         ret = 0;
 509                         break;
 510                 }
 511                 if (last < 0) {
 512                         ret = last;
 513                         break;
 514                 }
 515
 516                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 517                         dref = (struct btrfs_extent_data_ref *)(&eiref->offset);
 518                         ret = __data_list_add_eb(&data_refs, eb, dref);
 519                 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
 520                         logical = btrfs_extent_inline_ref_offset(eb, eiref);
 521                         ret = __shared_list_add(&shared_refs, logical);
 522                 }
 523         } while (!ret && !last);
 524
 525         /* ... then we proceed to in-tree references and ... */
 526         while (!ret) {
 527                 ++path->slots[0];
 528                 if (path->slots[0] > btrfs_header_nritems(eb)) {
 529                         ret = btrfs_next_leaf(fs_info->extent_root, path);
 530                         if (ret) {
 531                                 if (ret == 1)
 532                                         ret = 0; /* we're done */
 533                                 break;
 534                         }
 535                         eb = path->nodes[0];
 536                 }
 537                 btrfs_item_key_to_cpu(eb, &key, path->slots[0]);
 538                 if (key.objectid != extent_item_objectid)
 539                         break;
 540                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 541                         dref = btrfs_item_ptr(eb, path->slots[0],
 542                                                 struct btrfs_extent_data_ref);
 543                         ret = __data_list_add_eb(&data_refs, eb, dref);
 544                 } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 545                         ret = __shared_list_add(&shared_refs, key.offset);
 546                 }
 547         }
 548
 549         btrfs_release_path(path);
 550
 551         /*
 552          * ... only at the very end we can process the refs we found. this is
 553          * because the iterator function we call is allowed to make tree lookups
 554          * and we have to avoid deadlocks. additionally, we need more tree
 555          * lookups ourselves for shared data refs.
 556          */
 557         while (!list_empty(&data_refs)) {
 558                 ref_d = list_first_entry(&data_refs, struct __data_ref, list);
 559                 list_del(&ref_d->list);
 560                 if (!ret)
 561                         ret = iterate(ref_d->inum, extent_offset +
 562                                         ref_d->extent_data_item_offset,
 563                                         ref_d->root, ctx);
 564                 kfree(ref_d);
 565         }
 566
 567         while (!list_empty(&shared_refs)) {
 568                 ref_s = list_first_entry(&shared_refs, struct __shared_ref,
 569                                         list);
 570                 list_del(&ref_s->list);
 571                 if (!ret)
 572                         ret = __iter_shared_inline_ref(fs_info,
 573                                                         ref_s->disk_byte,
 574                                                         extent_item_objectid,
 575                                                         extent_offset, path,
 576                                                         &data_refs,
 577                                                         iterate, ctx);
 578                 kfree(ref_s);
 579         }
 580
 581         return ret;
 582 }
 583
 584 int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
 585                                 struct btrfs_path *path,
 586                                 iterate_extent_inodes_t *iterate, void *ctx)
 587 {
 588         int ret;
 589         u64 offset;
 590         struct btrfs_key found_key;
 591
 592         ret = extent_from_logical(fs_info, logical, path,
 593                                         &found_key);
 594         if (ret & BTRFS_EXTENT_FLAG_TREE_BLOCK)
 595                 ret = -EINVAL;
 596         if (ret < 0)
 597                 return ret;
 598
 599         offset = logical - found_key.objectid;
 600         ret = iterate_extent_inodes(fs_info, path, found_key.objectid,
 601                                         offset, iterate, ctx);
 602
 603         return ret;
 604 }
 605
 606 static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
 607                                 struct btrfs_path *path,
 608                                 iterate_irefs_t *iterate, void *ctx)
 609 {
 610         int ret;
 611         int slot;
 612         u32 cur;
 613         u32 len;
 614         u32 name_len;
 615         u64 parent = 0;
 616         int found = 0;
 617         struct extent_buffer *eb;
 618         struct btrfs_item *item;
 619         struct btrfs_inode_ref *iref;
 620         struct btrfs_key found_key;
 621
 622         while (1) {
 623                 ret = inode_ref_info(inum, parent ? parent+1 : 0, fs_root, path,
 624                                         &found_key);
 625                 if (ret < 0)
 626                         break;
 627                 if (ret) {
 628                         ret = found ? 0 : -ENOENT;
 629                         break;
 630                 }
 631                 ++found;
 632
 633                 parent = found_key.offset;
 634                 slot = path->slots[0];
 635                 eb = path->nodes[0];
 636                 /* make sure we can use eb after releasing the path */
 637                 atomic_inc(&eb->refs);
 638                 btrfs_release_path(path);
 639
 640                 item = btrfs_item_nr(eb, slot);
 641                 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 642
 643                 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
 644                         name_len = btrfs_inode_ref_name_len(eb, iref);
 645                         /* path must be released before calling iterate()! */
 646                         ret = iterate(parent, iref, eb, ctx);
 647                         if (ret) {
 648                                 free_extent_buffer(eb);
 649                                 break;
 650                         }
 651                         len = sizeof(*iref) + name_len;
 652                         iref = (struct btrfs_inode_ref *)((char *)iref + len);
 653                 }
 654                 free_extent_buffer(eb);
 655         }
 656
 657         btrfs_release_path(path);
 658
 659         return ret;
 660 }
 661
 662 /*
 663  * returns 0 if the path could be dumped (probably truncated)
 664  * returns <0 in case of an error
 665  */
 666 static int inode_to_path(u64 inum, struct btrfs_inode_ref *iref,
 667                                 struct extent_buffer *eb, void *ctx)
 668 {
 669         struct inode_fs_paths *ipath = ctx;
 670         char *fspath;
 671         char *fspath_min;
 672         int i = ipath->fspath->elem_cnt;
 673         const int s_ptr = sizeof(char *);
 674         u32 bytes_left;
 675
 676         bytes_left = ipath->fspath->bytes_left > s_ptr ?
 677                                         ipath->fspath->bytes_left - s_ptr : 0;
 678
 679         fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
 680         fspath = iref_to_path(ipath->fs_root, ipath->btrfs_path, iref, eb,
 681                                 inum, fspath_min, bytes_left);
 682         if (IS_ERR(fspath))
 683                 return PTR_ERR(fspath);
 684
 685         if (fspath > fspath_min) {
 686                 ipath->fspath->val[i] = (u64)(unsigned long)fspath;
 687                 ++ipath->fspath->elem_cnt;
 688                 ipath->fspath->bytes_left = fspath - fspath_min;
 689         } else {
 690                 ++ipath->fspath->elem_missed;
 691                 ipath->fspath->bytes_missing += fspath_min - fspath;
 692                 ipath->fspath->bytes_left = 0;
 693         }
 694
 695         return 0;
 696 }
 697
 698 /*
 699  * this dumps all file system paths to the inode into the ipath struct, provided
 700  * is has been created large enough. each path is zero-terminated and accessed
 701  * from ipath->fspath->val[i].
 702  * when it returns, there are ipath->fspath->elem_cnt number of paths available
 703  * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
 704  * number of missed paths in recored in ipath->fspath->elem_missed, otherwise,
 705  * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
 706  * have been needed to return all paths.
 707  */
 708 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
 709 {
 710         return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
 711                                 inode_to_path, ipath);
 712 }
 713
 714 /*
 715  * allocates space to return multiple file system paths for an inode.
 716  * total_bytes to allocate are passed, note that space usable for actual path
 717  * information will be total_bytes - sizeof(struct inode_fs_paths).
 718  * the returned pointer must be freed with free_ipath() in the end.
 719  */
 720 struct btrfs_data_container *init_data_container(u32 total_bytes)
 721 {
 722         struct btrfs_data_container *data;
 723         size_t alloc_bytes;
 724
 725         alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
 726         data = kmalloc(alloc_bytes, GFP_NOFS);
 727         if (!data)
 728                 return ERR_PTR(-ENOMEM);
 729
 730         if (total_bytes >= sizeof(*data)) {
 731                 data->bytes_left = total_bytes - sizeof(*data);
 732                 data->bytes_missing = 0;
 733         } else {
 734                 data->bytes_missing = sizeof(*data) - total_bytes;
 735                 data->bytes_left = 0;
 736         }
 737
 738         data->elem_cnt = 0;
 739         data->elem_missed = 0;
 740
 741         return data;
 742 }
 743
 744 /*
 745  * allocates space to return multiple file system paths for an inode.
 746  * total_bytes to allocate are passed, note that space usable for actual path
 747  * information will be total_bytes - sizeof(struct inode_fs_paths).
 748  * the returned pointer must be freed with free_ipath() in the end.
 749  */
 750 struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
 751                                         struct btrfs_path *path)
 752 {
 753         struct inode_fs_paths *ifp;
 754         struct btrfs_data_container *fspath;
 755
 756         fspath = init_data_container(total_bytes);
 757         if (IS_ERR(fspath))
 758                 return (void *)fspath;
 759
 760         ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
 761         if (!ifp) {
 762                 kfree(fspath);
 763                 return ERR_PTR(-ENOMEM);
 764         }
 765
 766         ifp->btrfs_path = path;
 767         ifp->fspath = fspath;
 768         ifp->fs_root = fs_root;
 769
 770         return ifp;
 771 }
 772
 773 void free_ipath(struct inode_fs_paths *ipath)
 774 {
 775         kfree(ipath);
 776 }