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