btrfs: added helper functions to iterate backrefs
[linux-3.10.git] / 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->str + (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->str[i] = 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->str[i].
702  * when it returns, there are ipath->fspath->elem_cnt number of paths available
703  * in ipath->fspath->str[]. 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 }