1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#include <linux/vmalloc.h>
20#include "ctree.h"
21#include "disk-io.h"
22#include "backref.h"
23#include "ulist.h"
24#include "transaction.h"
25#include "delayed-ref.h"
26#include "locking.h"
27
28struct extent_inode_elem {
29 u64 inum;
30 u64 offset;
31 struct extent_inode_elem *next;
32};
33
34static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
35 struct btrfs_file_extent_item *fi,
36 u64 extent_item_pos,
37 struct extent_inode_elem **eie)
38{
39 u64 offset = 0;
40 struct extent_inode_elem *e;
41
42 if (!btrfs_file_extent_compression(eb, fi) &&
43 !btrfs_file_extent_encryption(eb, fi) &&
44 !btrfs_file_extent_other_encoding(eb, fi)) {
45 u64 data_offset;
46 u64 data_len;
47
48 data_offset = btrfs_file_extent_offset(eb, fi);
49 data_len = btrfs_file_extent_num_bytes(eb, fi);
50
51 if (extent_item_pos < data_offset ||
52 extent_item_pos >= data_offset + data_len)
53 return 1;
54 offset = extent_item_pos - data_offset;
55 }
56
57 e = kmalloc(sizeof(*e), GFP_NOFS);
58 if (!e)
59 return -ENOMEM;
60
61 e->next = *eie;
62 e->inum = key->objectid;
63 e->offset = key->offset + offset;
64 *eie = e;
65
66 return 0;
67}
68
69static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
70 u64 extent_item_pos,
71 struct extent_inode_elem **eie)
72{
73 u64 disk_byte;
74 struct btrfs_key key;
75 struct btrfs_file_extent_item *fi;
76 int slot;
77 int nritems;
78 int extent_type;
79 int ret;
80
81
82
83
84
85
86 nritems = btrfs_header_nritems(eb);
87 for (slot = 0; slot < nritems; ++slot) {
88 btrfs_item_key_to_cpu(eb, &key, slot);
89 if (key.type != BTRFS_EXTENT_DATA_KEY)
90 continue;
91 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
92 extent_type = btrfs_file_extent_type(eb, fi);
93 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
94 continue;
95
96 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
97 if (disk_byte != wanted_disk_byte)
98 continue;
99
100 ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
101 if (ret < 0)
102 return ret;
103 }
104
105 return 0;
106}
107
108
109
110
111struct __prelim_ref {
112 struct list_head list;
113 u64 root_id;
114 struct btrfs_key key_for_search;
115 int level;
116 int count;
117 struct extent_inode_elem *inode_list;
118 u64 parent;
119 u64 wanted_disk_byte;
120};
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161static int __add_prelim_ref(struct list_head *head, u64 root_id,
162 struct btrfs_key *key, int level,
163 u64 parent, u64 wanted_disk_byte, int count)
164{
165 struct __prelim_ref *ref;
166
167
168 ref = kmalloc(sizeof(*ref), GFP_ATOMIC);
169 if (!ref)
170 return -ENOMEM;
171
172 ref->root_id = root_id;
173 if (key)
174 ref->key_for_search = *key;
175 else
176 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
177
178 ref->inode_list = NULL;
179 ref->level = level;
180 ref->count = count;
181 ref->parent = parent;
182 ref->wanted_disk_byte = wanted_disk_byte;
183 list_add_tail(&ref->list, head);
184
185 return 0;
186}
187
188static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
189 struct ulist *parents, int level,
190 struct btrfs_key *key_for_search, u64 time_seq,
191 u64 wanted_disk_byte,
192 const u64 *extent_item_pos)
193{
194 int ret = 0;
195 int slot;
196 struct extent_buffer *eb;
197 struct btrfs_key key;
198 struct btrfs_file_extent_item *fi;
199 struct extent_inode_elem *eie = NULL, *old = NULL;
200 u64 disk_byte;
201
202 if (level != 0) {
203 eb = path->nodes[level];
204 ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
205 if (ret < 0)
206 return ret;
207 return 0;
208 }
209
210
211
212
213
214
215 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
216 ret = btrfs_next_old_leaf(root, path, time_seq);
217
218 while (!ret) {
219 eb = path->nodes[0];
220 slot = path->slots[0];
221
222 btrfs_item_key_to_cpu(eb, &key, slot);
223
224 if (key.objectid != key_for_search->objectid ||
225 key.type != BTRFS_EXTENT_DATA_KEY)
226 break;
227
228 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
229 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
230
231 if (disk_byte == wanted_disk_byte) {
232 eie = NULL;
233 old = NULL;
234 if (extent_item_pos) {
235 ret = check_extent_in_eb(&key, eb, fi,
236 *extent_item_pos,
237 &eie);
238 if (ret < 0)
239 break;
240 }
241 if (ret > 0)
242 goto next;
243 ret = ulist_add_merge(parents, eb->start,
244 (uintptr_t)eie,
245 (u64 *)&old, GFP_NOFS);
246 if (ret < 0)
247 break;
248 if (!ret && extent_item_pos) {
249 while (old->next)
250 old = old->next;
251 old->next = eie;
252 }
253 }
254next:
255 ret = btrfs_next_old_item(root, path, time_seq);
256 }
257
258 if (ret > 0)
259 ret = 0;
260 return ret;
261}
262
263
264
265
266
267static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
268 struct btrfs_path *path, u64 time_seq,
269 struct __prelim_ref *ref,
270 struct ulist *parents,
271 const u64 *extent_item_pos)
272{
273 struct btrfs_root *root;
274 struct btrfs_key root_key;
275 struct extent_buffer *eb;
276 int ret = 0;
277 int root_level;
278 int level = ref->level;
279
280 root_key.objectid = ref->root_id;
281 root_key.type = BTRFS_ROOT_ITEM_KEY;
282 root_key.offset = (u64)-1;
283 root = btrfs_read_fs_root_no_name(fs_info, &root_key);
284 if (IS_ERR(root)) {
285 ret = PTR_ERR(root);
286 goto out;
287 }
288
289 root_level = btrfs_old_root_level(root, time_seq);
290
291 if (root_level + 1 == level)
292 goto out;
293
294 path->lowest_level = level;
295 ret = btrfs_search_old_slot(root, &ref->key_for_search, path, time_seq);
296 pr_debug("search slot in root %llu (level %d, ref count %d) returned "
297 "%d for key (%llu %u %llu)\n",
298 (unsigned long long)ref->root_id, level, ref->count, ret,
299 (unsigned long long)ref->key_for_search.objectid,
300 ref->key_for_search.type,
301 (unsigned long long)ref->key_for_search.offset);
302 if (ret < 0)
303 goto out;
304
305 eb = path->nodes[level];
306 while (!eb) {
307 if (!level) {
308 WARN_ON(1);
309 ret = 1;
310 goto out;
311 }
312 level--;
313 eb = path->nodes[level];
314 }
315
316 ret = add_all_parents(root, path, parents, level, &ref->key_for_search,
317 time_seq, ref->wanted_disk_byte,
318 extent_item_pos);
319out:
320 path->lowest_level = 0;
321 btrfs_release_path(path);
322 return ret;
323}
324
325
326
327
328static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
329 struct btrfs_path *path, u64 time_seq,
330 struct list_head *head,
331 const u64 *extent_item_pos)
332{
333 int err;
334 int ret = 0;
335 struct __prelim_ref *ref;
336 struct __prelim_ref *ref_safe;
337 struct __prelim_ref *new_ref;
338 struct ulist *parents;
339 struct ulist_node *node;
340 struct ulist_iterator uiter;
341
342 parents = ulist_alloc(GFP_NOFS);
343 if (!parents)
344 return -ENOMEM;
345
346
347
348
349
350
351 list_for_each_entry_safe(ref, ref_safe, head, list) {
352 if (ref->parent)
353 continue;
354 if (ref->count == 0)
355 continue;
356 err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
357 parents, extent_item_pos);
358 if (err == -ENOMEM)
359 goto out;
360 if (err)
361 continue;
362
363
364 ULIST_ITER_INIT(&uiter);
365 node = ulist_next(parents, &uiter);
366 ref->parent = node ? node->val : 0;
367 ref->inode_list = node ?
368 (struct extent_inode_elem *)(uintptr_t)node->aux : 0;
369
370
371 while ((node = ulist_next(parents, &uiter))) {
372 new_ref = kmalloc(sizeof(*new_ref), GFP_NOFS);
373 if (!new_ref) {
374 ret = -ENOMEM;
375 goto out;
376 }
377 memcpy(new_ref, ref, sizeof(*ref));
378 new_ref->parent = node->val;
379 new_ref->inode_list = (struct extent_inode_elem *)
380 (uintptr_t)node->aux;
381 list_add(&new_ref->list, &ref->list);
382 }
383 ulist_reinit(parents);
384 }
385out:
386 ulist_free(parents);
387 return ret;
388}
389
390static inline int ref_for_same_block(struct __prelim_ref *ref1,
391 struct __prelim_ref *ref2)
392{
393 if (ref1->level != ref2->level)
394 return 0;
395 if (ref1->root_id != ref2->root_id)
396 return 0;
397 if (ref1->key_for_search.type != ref2->key_for_search.type)
398 return 0;
399 if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
400 return 0;
401 if (ref1->key_for_search.offset != ref2->key_for_search.offset)
402 return 0;
403 if (ref1->parent != ref2->parent)
404 return 0;
405
406 return 1;
407}
408
409
410
411
412static int __add_missing_keys(struct btrfs_fs_info *fs_info,
413 struct list_head *head)
414{
415 struct list_head *pos;
416 struct extent_buffer *eb;
417
418 list_for_each(pos, head) {
419 struct __prelim_ref *ref;
420 ref = list_entry(pos, struct __prelim_ref, list);
421
422 if (ref->parent)
423 continue;
424 if (ref->key_for_search.type)
425 continue;
426 BUG_ON(!ref->wanted_disk_byte);
427 eb = read_tree_block(fs_info->tree_root, ref->wanted_disk_byte,
428 fs_info->tree_root->leafsize, 0);
429 if (!eb || !extent_buffer_uptodate(eb)) {
430 free_extent_buffer(eb);
431 return -EIO;
432 }
433 btrfs_tree_read_lock(eb);
434 if (btrfs_header_level(eb) == 0)
435 btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
436 else
437 btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
438 btrfs_tree_read_unlock(eb);
439 free_extent_buffer(eb);
440 }
441 return 0;
442}
443
444
445
446
447
448
449
450
451
452
453
454static void __merge_refs(struct list_head *head, int mode)
455{
456 struct list_head *pos1;
457
458 list_for_each(pos1, head) {
459 struct list_head *n2;
460 struct list_head *pos2;
461 struct __prelim_ref *ref1;
462
463 ref1 = list_entry(pos1, struct __prelim_ref, list);
464
465 for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
466 pos2 = n2, n2 = pos2->next) {
467 struct __prelim_ref *ref2;
468 struct __prelim_ref *xchg;
469 struct extent_inode_elem *eie;
470
471 ref2 = list_entry(pos2, struct __prelim_ref, list);
472
473 if (mode == 1) {
474 if (!ref_for_same_block(ref1, ref2))
475 continue;
476 if (!ref1->parent && ref2->parent) {
477 xchg = ref1;
478 ref1 = ref2;
479 ref2 = xchg;
480 }
481 } else {
482 if (ref1->parent != ref2->parent)
483 continue;
484 }
485
486 eie = ref1->inode_list;
487 while (eie && eie->next)
488 eie = eie->next;
489 if (eie)
490 eie->next = ref2->inode_list;
491 else
492 ref1->inode_list = ref2->inode_list;
493 ref1->count += ref2->count;
494
495 list_del(&ref2->list);
496 kfree(ref2);
497 }
498
499 }
500}
501
502
503
504
505
506static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
507 struct list_head *prefs)
508{
509 struct btrfs_delayed_extent_op *extent_op = head->extent_op;
510 struct rb_node *n = &head->node.rb_node;
511 struct btrfs_key key;
512 struct btrfs_key op_key = {0};
513 int sgn;
514 int ret = 0;
515
516 if (extent_op && extent_op->update_key)
517 btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
518
519 while ((n = rb_prev(n))) {
520 struct btrfs_delayed_ref_node *node;
521 node = rb_entry(n, struct btrfs_delayed_ref_node,
522 rb_node);
523 if (node->bytenr != head->node.bytenr)
524 break;
525 WARN_ON(node->is_head);
526
527 if (node->seq > seq)
528 continue;
529
530 switch (node->action) {
531 case BTRFS_ADD_DELAYED_EXTENT:
532 case BTRFS_UPDATE_DELAYED_HEAD:
533 WARN_ON(1);
534 continue;
535 case BTRFS_ADD_DELAYED_REF:
536 sgn = 1;
537 break;
538 case BTRFS_DROP_DELAYED_REF:
539 sgn = -1;
540 break;
541 default:
542 BUG_ON(1);
543 }
544 switch (node->type) {
545 case BTRFS_TREE_BLOCK_REF_KEY: {
546 struct btrfs_delayed_tree_ref *ref;
547
548 ref = btrfs_delayed_node_to_tree_ref(node);
549 ret = __add_prelim_ref(prefs, ref->root, &op_key,
550 ref->level + 1, 0, node->bytenr,
551 node->ref_mod * sgn);
552 break;
553 }
554 case BTRFS_SHARED_BLOCK_REF_KEY: {
555 struct btrfs_delayed_tree_ref *ref;
556
557 ref = btrfs_delayed_node_to_tree_ref(node);
558 ret = __add_prelim_ref(prefs, ref->root, NULL,
559 ref->level + 1, ref->parent,
560 node->bytenr,
561 node->ref_mod * sgn);
562 break;
563 }
564 case BTRFS_EXTENT_DATA_REF_KEY: {
565 struct btrfs_delayed_data_ref *ref;
566 ref = btrfs_delayed_node_to_data_ref(node);
567
568 key.objectid = ref->objectid;
569 key.type = BTRFS_EXTENT_DATA_KEY;
570 key.offset = ref->offset;
571 ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
572 node->bytenr,
573 node->ref_mod * sgn);
574 break;
575 }
576 case BTRFS_SHARED_DATA_REF_KEY: {
577 struct btrfs_delayed_data_ref *ref;
578
579 ref = btrfs_delayed_node_to_data_ref(node);
580
581 key.objectid = ref->objectid;
582 key.type = BTRFS_EXTENT_DATA_KEY;
583 key.offset = ref->offset;
584 ret = __add_prelim_ref(prefs, ref->root, &key, 0,
585 ref->parent, node->bytenr,
586 node->ref_mod * sgn);
587 break;
588 }
589 default:
590 WARN_ON(1);
591 }
592 if (ret)
593 return ret;
594 }
595
596 return 0;
597}
598
599
600
601
602static int __add_inline_refs(struct btrfs_fs_info *fs_info,
603 struct btrfs_path *path, u64 bytenr,
604 int *info_level, struct list_head *prefs)
605{
606 int ret = 0;
607 int slot;
608 struct extent_buffer *leaf;
609 struct btrfs_key key;
610 struct btrfs_key found_key;
611 unsigned long ptr;
612 unsigned long end;
613 struct btrfs_extent_item *ei;
614 u64 flags;
615 u64 item_size;
616
617
618
619
620 leaf = path->nodes[0];
621 slot = path->slots[0];
622
623 item_size = btrfs_item_size_nr(leaf, slot);
624 BUG_ON(item_size < sizeof(*ei));
625
626 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
627 flags = btrfs_extent_flags(leaf, ei);
628 btrfs_item_key_to_cpu(leaf, &found_key, slot);
629
630 ptr = (unsigned long)(ei + 1);
631 end = (unsigned long)ei + item_size;
632
633 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
634 flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
635 struct btrfs_tree_block_info *info;
636
637 info = (struct btrfs_tree_block_info *)ptr;
638 *info_level = btrfs_tree_block_level(leaf, info);
639 ptr += sizeof(struct btrfs_tree_block_info);
640 BUG_ON(ptr > end);
641 } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
642 *info_level = found_key.offset;
643 } else {
644 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
645 }
646
647 while (ptr < end) {
648 struct btrfs_extent_inline_ref *iref;
649 u64 offset;
650 int type;
651
652 iref = (struct btrfs_extent_inline_ref *)ptr;
653 type = btrfs_extent_inline_ref_type(leaf, iref);
654 offset = btrfs_extent_inline_ref_offset(leaf, iref);
655
656 switch (type) {
657 case BTRFS_SHARED_BLOCK_REF_KEY:
658 ret = __add_prelim_ref(prefs, 0, NULL,
659 *info_level + 1, offset,
660 bytenr, 1);
661 break;
662 case BTRFS_SHARED_DATA_REF_KEY: {
663 struct btrfs_shared_data_ref *sdref;
664 int count;
665
666 sdref = (struct btrfs_shared_data_ref *)(iref + 1);
667 count = btrfs_shared_data_ref_count(leaf, sdref);
668 ret = __add_prelim_ref(prefs, 0, NULL, 0, offset,
669 bytenr, count);
670 break;
671 }
672 case BTRFS_TREE_BLOCK_REF_KEY:
673 ret = __add_prelim_ref(prefs, offset, NULL,
674 *info_level + 1, 0,
675 bytenr, 1);
676 break;
677 case BTRFS_EXTENT_DATA_REF_KEY: {
678 struct btrfs_extent_data_ref *dref;
679 int count;
680 u64 root;
681
682 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
683 count = btrfs_extent_data_ref_count(leaf, dref);
684 key.objectid = btrfs_extent_data_ref_objectid(leaf,
685 dref);
686 key.type = BTRFS_EXTENT_DATA_KEY;
687 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
688 root = btrfs_extent_data_ref_root(leaf, dref);
689 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
690 bytenr, count);
691 break;
692 }
693 default:
694 WARN_ON(1);
695 }
696 if (ret)
697 return ret;
698 ptr += btrfs_extent_inline_ref_size(type);
699 }
700
701 return 0;
702}
703
704
705
706
707static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
708 struct btrfs_path *path, u64 bytenr,
709 int info_level, struct list_head *prefs)
710{
711 struct btrfs_root *extent_root = fs_info->extent_root;
712 int ret;
713 int slot;
714 struct extent_buffer *leaf;
715 struct btrfs_key key;
716
717 while (1) {
718 ret = btrfs_next_item(extent_root, path);
719 if (ret < 0)
720 break;
721 if (ret) {
722 ret = 0;
723 break;
724 }
725
726 slot = path->slots[0];
727 leaf = path->nodes[0];
728 btrfs_item_key_to_cpu(leaf, &key, slot);
729
730 if (key.objectid != bytenr)
731 break;
732 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
733 continue;
734 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
735 break;
736
737 switch (key.type) {
738 case BTRFS_SHARED_BLOCK_REF_KEY:
739 ret = __add_prelim_ref(prefs, 0, NULL,
740 info_level + 1, key.offset,
741 bytenr, 1);
742 break;
743 case BTRFS_SHARED_DATA_REF_KEY: {
744 struct btrfs_shared_data_ref *sdref;
745 int count;
746
747 sdref = btrfs_item_ptr(leaf, slot,
748 struct btrfs_shared_data_ref);
749 count = btrfs_shared_data_ref_count(leaf, sdref);
750 ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset,
751 bytenr, count);
752 break;
753 }
754 case BTRFS_TREE_BLOCK_REF_KEY:
755 ret = __add_prelim_ref(prefs, key.offset, NULL,
756 info_level + 1, 0,
757 bytenr, 1);
758 break;
759 case BTRFS_EXTENT_DATA_REF_KEY: {
760 struct btrfs_extent_data_ref *dref;
761 int count;
762 u64 root;
763
764 dref = btrfs_item_ptr(leaf, slot,
765 struct btrfs_extent_data_ref);
766 count = btrfs_extent_data_ref_count(leaf, dref);
767 key.objectid = btrfs_extent_data_ref_objectid(leaf,
768 dref);
769 key.type = BTRFS_EXTENT_DATA_KEY;
770 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
771 root = btrfs_extent_data_ref_root(leaf, dref);
772 ret = __add_prelim_ref(prefs, root, &key, 0, 0,
773 bytenr, count);
774 break;
775 }
776 default:
777 WARN_ON(1);
778 }
779 if (ret)
780 return ret;
781
782 }
783
784 return ret;
785}
786
787
788
789
790
791
792
793
794
795static int find_parent_nodes(struct btrfs_trans_handle *trans,
796 struct btrfs_fs_info *fs_info, u64 bytenr,
797 u64 time_seq, struct ulist *refs,
798 struct ulist *roots, const u64 *extent_item_pos)
799{
800 struct btrfs_key key;
801 struct btrfs_path *path;
802 struct btrfs_delayed_ref_root *delayed_refs = NULL;
803 struct btrfs_delayed_ref_head *head;
804 int info_level = 0;
805 int ret;
806 struct list_head prefs_delayed;
807 struct list_head prefs;
808 struct __prelim_ref *ref;
809
810 INIT_LIST_HEAD(&prefs);
811 INIT_LIST_HEAD(&prefs_delayed);
812
813 key.objectid = bytenr;
814 key.offset = (u64)-1;
815 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
816 key.type = BTRFS_METADATA_ITEM_KEY;
817 else
818 key.type = BTRFS_EXTENT_ITEM_KEY;
819
820 path = btrfs_alloc_path();
821 if (!path)
822 return -ENOMEM;
823 if (!trans)
824 path->search_commit_root = 1;
825
826
827
828
829
830
831again:
832 head = NULL;
833
834 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
835 if (ret < 0)
836 goto out;
837 BUG_ON(ret == 0);
838
839 if (trans) {
840
841
842
843
844 delayed_refs = &trans->transaction->delayed_refs;
845 spin_lock(&delayed_refs->lock);
846 head = btrfs_find_delayed_ref_head(trans, bytenr);
847 if (head) {
848 if (!mutex_trylock(&head->mutex)) {
849 atomic_inc(&head->node.refs);
850 spin_unlock(&delayed_refs->lock);
851
852 btrfs_release_path(path);
853
854
855
856
857
858 mutex_lock(&head->mutex);
859 mutex_unlock(&head->mutex);
860 btrfs_put_delayed_ref(&head->node);
861 goto again;
862 }
863 ret = __add_delayed_refs(head, time_seq,
864 &prefs_delayed);
865 mutex_unlock(&head->mutex);
866 if (ret) {
867 spin_unlock(&delayed_refs->lock);
868 goto out;
869 }
870 }
871 spin_unlock(&delayed_refs->lock);
872 }
873
874 if (path->slots[0]) {
875 struct extent_buffer *leaf;
876 int slot;
877
878 path->slots[0]--;
879 leaf = path->nodes[0];
880 slot = path->slots[0];
881 btrfs_item_key_to_cpu(leaf, &key, slot);
882 if (key.objectid == bytenr &&
883 (key.type == BTRFS_EXTENT_ITEM_KEY ||
884 key.type == BTRFS_METADATA_ITEM_KEY)) {
885 ret = __add_inline_refs(fs_info, path, bytenr,
886 &info_level, &prefs);
887 if (ret)
888 goto out;
889 ret = __add_keyed_refs(fs_info, path, bytenr,
890 info_level, &prefs);
891 if (ret)
892 goto out;
893 }
894 }
895 btrfs_release_path(path);
896
897 list_splice_init(&prefs_delayed, &prefs);
898
899 ret = __add_missing_keys(fs_info, &prefs);
900 if (ret)
901 goto out;
902
903 __merge_refs(&prefs, 1);
904
905 ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
906 extent_item_pos);
907 if (ret)
908 goto out;
909
910 __merge_refs(&prefs, 2);
911
912 while (!list_empty(&prefs)) {
913 ref = list_first_entry(&prefs, struct __prelim_ref, list);
914 list_del(&ref->list);
915 WARN_ON(ref->count < 0);
916 if (ref->count && ref->root_id && ref->parent == 0) {
917
918 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
919 if (ret < 0)
920 goto out;
921 }
922 if (ref->count && ref->parent) {
923 struct extent_inode_elem *eie = NULL;
924 if (extent_item_pos && !ref->inode_list) {
925 u32 bsz;
926 struct extent_buffer *eb;
927 bsz = btrfs_level_size(fs_info->extent_root,
928 info_level);
929 eb = read_tree_block(fs_info->extent_root,
930 ref->parent, bsz, 0);
931 if (!eb || !extent_buffer_uptodate(eb)) {
932 free_extent_buffer(eb);
933 ret = -EIO;
934 goto out;
935 }
936 ret = find_extent_in_eb(eb, bytenr,
937 *extent_item_pos, &eie);
938 ref->inode_list = eie;
939 free_extent_buffer(eb);
940 }
941 ret = ulist_add_merge(refs, ref->parent,
942 (uintptr_t)ref->inode_list,
943 (u64 *)&eie, GFP_NOFS);
944 if (ret < 0)
945 goto out;
946 if (!ret && extent_item_pos) {
947
948
949
950
951 BUG_ON(!eie);
952 while (eie->next)
953 eie = eie->next;
954 eie->next = ref->inode_list;
955 }
956 }
957 kfree(ref);
958 }
959
960out:
961 btrfs_free_path(path);
962 while (!list_empty(&prefs)) {
963 ref = list_first_entry(&prefs, struct __prelim_ref, list);
964 list_del(&ref->list);
965 kfree(ref);
966 }
967 while (!list_empty(&prefs_delayed)) {
968 ref = list_first_entry(&prefs_delayed, struct __prelim_ref,
969 list);
970 list_del(&ref->list);
971 kfree(ref);
972 }
973
974 return ret;
975}
976
977static void free_leaf_list(struct ulist *blocks)
978{
979 struct ulist_node *node = NULL;
980 struct extent_inode_elem *eie;
981 struct extent_inode_elem *eie_next;
982 struct ulist_iterator uiter;
983
984 ULIST_ITER_INIT(&uiter);
985 while ((node = ulist_next(blocks, &uiter))) {
986 if (!node->aux)
987 continue;
988 eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
989 for (; eie; eie = eie_next) {
990 eie_next = eie->next;
991 kfree(eie);
992 }
993 node->aux = 0;
994 }
995
996 ulist_free(blocks);
997}
998
999
1000
1001
1002
1003
1004
1005
1006
1007static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
1008 struct btrfs_fs_info *fs_info, u64 bytenr,
1009 u64 time_seq, struct ulist **leafs,
1010 const u64 *extent_item_pos)
1011{
1012 struct ulist *tmp;
1013 int ret;
1014
1015 tmp = ulist_alloc(GFP_NOFS);
1016 if (!tmp)
1017 return -ENOMEM;
1018 *leafs = ulist_alloc(GFP_NOFS);
1019 if (!*leafs) {
1020 ulist_free(tmp);
1021 return -ENOMEM;
1022 }
1023
1024 ret = find_parent_nodes(trans, fs_info, bytenr,
1025 time_seq, *leafs, tmp, extent_item_pos);
1026 ulist_free(tmp);
1027
1028 if (ret < 0 && ret != -ENOENT) {
1029 free_leaf_list(*leafs);
1030 return ret;
1031 }
1032
1033 return 0;
1034}
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
1050 struct btrfs_fs_info *fs_info, u64 bytenr,
1051 u64 time_seq, struct ulist **roots)
1052{
1053 struct ulist *tmp;
1054 struct ulist_node *node = NULL;
1055 struct ulist_iterator uiter;
1056 int ret;
1057
1058 tmp = ulist_alloc(GFP_NOFS);
1059 if (!tmp)
1060 return -ENOMEM;
1061 *roots = ulist_alloc(GFP_NOFS);
1062 if (!*roots) {
1063 ulist_free(tmp);
1064 return -ENOMEM;
1065 }
1066
1067 ULIST_ITER_INIT(&uiter);
1068 while (1) {
1069 ret = find_parent_nodes(trans, fs_info, bytenr,
1070 time_seq, tmp, *roots, NULL);
1071 if (ret < 0 && ret != -ENOENT) {
1072 ulist_free(tmp);
1073 ulist_free(*roots);
1074 return ret;
1075 }
1076 node = ulist_next(tmp, &uiter);
1077 if (!node)
1078 break;
1079 bytenr = node->val;
1080 }
1081
1082 ulist_free(tmp);
1083 return 0;
1084}
1085
1086
1087static int __inode_info(u64 inum, u64 ioff, u8 key_type,
1088 struct btrfs_root *fs_root, struct btrfs_path *path,
1089 struct btrfs_key *found_key)
1090{
1091 int ret;
1092 struct btrfs_key key;
1093 struct extent_buffer *eb;
1094
1095 key.type = key_type;
1096 key.objectid = inum;
1097 key.offset = ioff;
1098
1099 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
1100 if (ret < 0)
1101 return ret;
1102
1103 eb = path->nodes[0];
1104 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1105 ret = btrfs_next_leaf(fs_root, path);
1106 if (ret)
1107 return ret;
1108 eb = path->nodes[0];
1109 }
1110
1111 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
1112 if (found_key->type != key.type || found_key->objectid != key.objectid)
1113 return 1;
1114
1115 return 0;
1116}
1117
1118
1119
1120
1121int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
1122 struct btrfs_path *path)
1123{
1124 struct btrfs_key key;
1125 return __inode_info(inum, ioff, BTRFS_INODE_ITEM_KEY, fs_root, path,
1126 &key);
1127}
1128
1129static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
1130 struct btrfs_path *path,
1131 struct btrfs_key *found_key)
1132{
1133 return __inode_info(inum, ioff, BTRFS_INODE_REF_KEY, fs_root, path,
1134 found_key);
1135}
1136
1137int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
1138 u64 start_off, struct btrfs_path *path,
1139 struct btrfs_inode_extref **ret_extref,
1140 u64 *found_off)
1141{
1142 int ret, slot;
1143 struct btrfs_key key;
1144 struct btrfs_key found_key;
1145 struct btrfs_inode_extref *extref;
1146 struct extent_buffer *leaf;
1147 unsigned long ptr;
1148
1149 key.objectid = inode_objectid;
1150 btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY);
1151 key.offset = start_off;
1152
1153 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1154 if (ret < 0)
1155 return ret;
1156
1157 while (1) {
1158 leaf = path->nodes[0];
1159 slot = path->slots[0];
1160 if (slot >= btrfs_header_nritems(leaf)) {
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170 ret = btrfs_next_leaf(root, path);
1171 if (ret) {
1172 if (ret >= 1)
1173 ret = -ENOENT;
1174 break;
1175 }
1176 continue;
1177 }
1178
1179 btrfs_item_key_to_cpu(leaf, &found_key, slot);
1180
1181
1182
1183
1184
1185
1186
1187 ret = -ENOENT;
1188 if (found_key.objectid != inode_objectid)
1189 break;
1190 if (btrfs_key_type(&found_key) != BTRFS_INODE_EXTREF_KEY)
1191 break;
1192
1193 ret = 0;
1194 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1195 extref = (struct btrfs_inode_extref *)ptr;
1196 *ret_extref = extref;
1197 if (found_off)
1198 *found_off = found_key.offset;
1199 break;
1200 }
1201
1202 return ret;
1203}
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
1220 u32 name_len, unsigned long name_off,
1221 struct extent_buffer *eb_in, u64 parent,
1222 char *dest, u32 size)
1223{
1224 int slot;
1225 u64 next_inum;
1226 int ret;
1227 s64 bytes_left = ((s64)size) - 1;
1228 struct extent_buffer *eb = eb_in;
1229 struct btrfs_key found_key;
1230 int leave_spinning = path->leave_spinning;
1231 struct btrfs_inode_ref *iref;
1232
1233 if (bytes_left >= 0)
1234 dest[bytes_left] = '\0';
1235
1236 path->leave_spinning = 1;
1237 while (1) {
1238 bytes_left -= name_len;
1239 if (bytes_left >= 0)
1240 read_extent_buffer(eb, dest + bytes_left,
1241 name_off, name_len);
1242 if (eb != eb_in) {
1243 btrfs_tree_read_unlock_blocking(eb);
1244 free_extent_buffer(eb);
1245 }
1246 ret = inode_ref_info(parent, 0, fs_root, path, &found_key);
1247 if (ret > 0)
1248 ret = -ENOENT;
1249 if (ret)
1250 break;
1251
1252 next_inum = found_key.offset;
1253
1254
1255 if (parent == next_inum)
1256 break;
1257
1258 slot = path->slots[0];
1259 eb = path->nodes[0];
1260
1261 if (eb != eb_in) {
1262 atomic_inc(&eb->refs);
1263 btrfs_tree_read_lock(eb);
1264 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1265 }
1266 btrfs_release_path(path);
1267 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1268
1269 name_len = btrfs_inode_ref_name_len(eb, iref);
1270 name_off = (unsigned long)(iref + 1);
1271
1272 parent = next_inum;
1273 --bytes_left;
1274 if (bytes_left >= 0)
1275 dest[bytes_left] = '/';
1276 }
1277
1278 btrfs_release_path(path);
1279 path->leave_spinning = leave_spinning;
1280
1281 if (ret)
1282 return ERR_PTR(ret);
1283
1284 return dest + bytes_left;
1285}
1286
1287
1288
1289
1290
1291
1292int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1293 struct btrfs_path *path, struct btrfs_key *found_key,
1294 u64 *flags_ret)
1295{
1296 int ret;
1297 u64 flags;
1298 u64 size = 0;
1299 u32 item_size;
1300 struct extent_buffer *eb;
1301 struct btrfs_extent_item *ei;
1302 struct btrfs_key key;
1303
1304 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1305 key.type = BTRFS_METADATA_ITEM_KEY;
1306 else
1307 key.type = BTRFS_EXTENT_ITEM_KEY;
1308 key.objectid = logical;
1309 key.offset = (u64)-1;
1310
1311 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1312 if (ret < 0)
1313 return ret;
1314 ret = btrfs_previous_item(fs_info->extent_root, path,
1315 0, BTRFS_EXTENT_ITEM_KEY);
1316 if (ret < 0)
1317 return ret;
1318
1319 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1320 if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1321 size = fs_info->extent_root->leafsize;
1322 else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
1323 size = found_key->offset;
1324
1325 if ((found_key->type != BTRFS_EXTENT_ITEM_KEY &&
1326 found_key->type != BTRFS_METADATA_ITEM_KEY) ||
1327 found_key->objectid > logical ||
1328 found_key->objectid + size <= logical) {
1329 pr_debug("logical %llu is not within any extent\n",
1330 (unsigned long long)logical);
1331 return -ENOENT;
1332 }
1333
1334 eb = path->nodes[0];
1335 item_size = btrfs_item_size_nr(eb, path->slots[0]);
1336 BUG_ON(item_size < sizeof(*ei));
1337
1338 ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
1339 flags = btrfs_extent_flags(eb, ei);
1340
1341 pr_debug("logical %llu is at position %llu within the extent (%llu "
1342 "EXTENT_ITEM %llu) flags %#llx size %u\n",
1343 (unsigned long long)logical,
1344 (unsigned long long)(logical - found_key->objectid),
1345 (unsigned long long)found_key->objectid,
1346 (unsigned long long)found_key->offset,
1347 (unsigned long long)flags, item_size);
1348
1349 WARN_ON(!flags_ret);
1350 if (flags_ret) {
1351 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1352 *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
1353 else if (flags & BTRFS_EXTENT_FLAG_DATA)
1354 *flags_ret = BTRFS_EXTENT_FLAG_DATA;
1355 else
1356 BUG_ON(1);
1357 return 0;
1358 }
1359
1360 return -EIO;
1361}
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
1372 struct btrfs_extent_item *ei, u32 item_size,
1373 struct btrfs_extent_inline_ref **out_eiref,
1374 int *out_type)
1375{
1376 unsigned long end;
1377 u64 flags;
1378 struct btrfs_tree_block_info *info;
1379
1380 if (!*ptr) {
1381
1382 flags = btrfs_extent_flags(eb, ei);
1383 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1384 info = (struct btrfs_tree_block_info *)(ei + 1);
1385 *out_eiref =
1386 (struct btrfs_extent_inline_ref *)(info + 1);
1387 } else {
1388 *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
1389 }
1390 *ptr = (unsigned long)*out_eiref;
1391 if ((void *)*ptr >= (void *)ei + item_size)
1392 return -ENOENT;
1393 }
1394
1395 end = (unsigned long)ei + item_size;
1396 *out_eiref = (struct btrfs_extent_inline_ref *)*ptr;
1397 *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);
1398
1399 *ptr += btrfs_extent_inline_ref_size(*out_type);
1400 WARN_ON(*ptr > end);
1401 if (*ptr == end)
1402 return 1;
1403
1404 return 0;
1405}
1406
1407
1408
1409
1410
1411
1412
1413
1414int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
1415 struct btrfs_extent_item *ei, u32 item_size,
1416 u64 *out_root, u8 *out_level)
1417{
1418 int ret;
1419 int type;
1420 struct btrfs_tree_block_info *info;
1421 struct btrfs_extent_inline_ref *eiref;
1422
1423 if (*ptr == (unsigned long)-1)
1424 return 1;
1425
1426 while (1) {
1427 ret = __get_extent_inline_ref(ptr, eb, ei, item_size,
1428 &eiref, &type);
1429 if (ret < 0)
1430 return ret;
1431
1432 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1433 type == BTRFS_SHARED_BLOCK_REF_KEY)
1434 break;
1435
1436 if (ret == 1)
1437 return 1;
1438 }
1439
1440
1441 info = (struct btrfs_tree_block_info *)(ei + 1);
1442 *out_root = btrfs_extent_inline_ref_offset(eb, eiref);
1443 *out_level = btrfs_tree_block_level(eb, info);
1444
1445 if (ret == 1)
1446 *ptr = (unsigned long)-1;
1447
1448 return 0;
1449}
1450
1451static int iterate_leaf_refs(struct extent_inode_elem *inode_list,
1452 u64 root, u64 extent_item_objectid,
1453 iterate_extent_inodes_t *iterate, void *ctx)
1454{
1455 struct extent_inode_elem *eie;
1456 int ret = 0;
1457
1458 for (eie = inode_list; eie; eie = eie->next) {
1459 pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
1460 "root %llu\n", extent_item_objectid,
1461 eie->inum, eie->offset, root);
1462 ret = iterate(eie->inum, eie->offset, root, ctx);
1463 if (ret) {
1464 pr_debug("stopping iteration for %llu due to ret=%d\n",
1465 extent_item_objectid, ret);
1466 break;
1467 }
1468 }
1469
1470 return ret;
1471}
1472
1473
1474
1475
1476
1477
1478int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
1479 u64 extent_item_objectid, u64 extent_item_pos,
1480 int search_commit_root,
1481 iterate_extent_inodes_t *iterate, void *ctx)
1482{
1483 int ret;
1484 struct btrfs_trans_handle *trans = NULL;
1485 struct ulist *refs = NULL;
1486 struct ulist *roots = NULL;
1487 struct ulist_node *ref_node = NULL;
1488 struct ulist_node *root_node = NULL;
1489 struct seq_list tree_mod_seq_elem = {};
1490 struct ulist_iterator ref_uiter;
1491 struct ulist_iterator root_uiter;
1492
1493 pr_debug("resolving all inodes for extent %llu\n",
1494 extent_item_objectid);
1495
1496 if (!search_commit_root) {
1497 trans = btrfs_join_transaction(fs_info->extent_root);
1498 if (IS_ERR(trans))
1499 return PTR_ERR(trans);
1500 btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1501 }
1502
1503 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1504 tree_mod_seq_elem.seq, &refs,
1505 &extent_item_pos);
1506 if (ret)
1507 goto out;
1508
1509 ULIST_ITER_INIT(&ref_uiter);
1510 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1511 ret = btrfs_find_all_roots(trans, fs_info, ref_node->val,
1512 tree_mod_seq_elem.seq, &roots);
1513 if (ret)
1514 break;
1515 ULIST_ITER_INIT(&root_uiter);
1516 while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1517 pr_debug("root %llu references leaf %llu, data list "
1518 "%#llx\n", root_node->val, ref_node->val,
1519 (long long)ref_node->aux);
1520 ret = iterate_leaf_refs((struct extent_inode_elem *)
1521 (uintptr_t)ref_node->aux,
1522 root_node->val,
1523 extent_item_objectid,
1524 iterate, ctx);
1525 }
1526 ulist_free(roots);
1527 }
1528
1529 free_leaf_list(refs);
1530out:
1531 if (!search_commit_root) {
1532 btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1533 btrfs_end_transaction(trans, fs_info->extent_root);
1534 }
1535
1536 return ret;
1537}
1538
1539int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
1540 struct btrfs_path *path,
1541 iterate_extent_inodes_t *iterate, void *ctx)
1542{
1543 int ret;
1544 u64 extent_item_pos;
1545 u64 flags = 0;
1546 struct btrfs_key found_key;
1547 int search_commit_root = path->search_commit_root;
1548
1549 ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
1550 btrfs_release_path(path);
1551 if (ret < 0)
1552 return ret;
1553 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1554 return -EINVAL;
1555
1556 extent_item_pos = logical - found_key.objectid;
1557 ret = iterate_extent_inodes(fs_info, found_key.objectid,
1558 extent_item_pos, search_commit_root,
1559 iterate, ctx);
1560
1561 return ret;
1562}
1563
1564typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
1565 struct extent_buffer *eb, void *ctx);
1566
1567static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
1568 struct btrfs_path *path,
1569 iterate_irefs_t *iterate, void *ctx)
1570{
1571 int ret = 0;
1572 int slot;
1573 u32 cur;
1574 u32 len;
1575 u32 name_len;
1576 u64 parent = 0;
1577 int found = 0;
1578 struct extent_buffer *eb;
1579 struct btrfs_item *item;
1580 struct btrfs_inode_ref *iref;
1581 struct btrfs_key found_key;
1582
1583 while (!ret) {
1584 path->leave_spinning = 1;
1585 ret = inode_ref_info(inum, parent ? parent+1 : 0, fs_root, path,
1586 &found_key);
1587 if (ret < 0)
1588 break;
1589 if (ret) {
1590 ret = found ? 0 : -ENOENT;
1591 break;
1592 }
1593 ++found;
1594
1595 parent = found_key.offset;
1596 slot = path->slots[0];
1597 eb = path->nodes[0];
1598
1599 atomic_inc(&eb->refs);
1600 btrfs_tree_read_lock(eb);
1601 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1602 btrfs_release_path(path);
1603
1604 item = btrfs_item_nr(eb, slot);
1605 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1606
1607 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
1608 name_len = btrfs_inode_ref_name_len(eb, iref);
1609
1610 pr_debug("following ref at offset %u for inode %llu in "
1611 "tree %llu\n", cur,
1612 (unsigned long long)found_key.objectid,
1613 (unsigned long long)fs_root->objectid);
1614 ret = iterate(parent, name_len,
1615 (unsigned long)(iref + 1), eb, ctx);
1616 if (ret)
1617 break;
1618 len = sizeof(*iref) + name_len;
1619 iref = (struct btrfs_inode_ref *)((char *)iref + len);
1620 }
1621 btrfs_tree_read_unlock_blocking(eb);
1622 free_extent_buffer(eb);
1623 }
1624
1625 btrfs_release_path(path);
1626
1627 return ret;
1628}
1629
1630static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
1631 struct btrfs_path *path,
1632 iterate_irefs_t *iterate, void *ctx)
1633{
1634 int ret;
1635 int slot;
1636 u64 offset = 0;
1637 u64 parent;
1638 int found = 0;
1639 struct extent_buffer *eb;
1640 struct btrfs_inode_extref *extref;
1641 struct extent_buffer *leaf;
1642 u32 item_size;
1643 u32 cur_offset;
1644 unsigned long ptr;
1645
1646 while (1) {
1647 ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
1648 &offset);
1649 if (ret < 0)
1650 break;
1651 if (ret) {
1652 ret = found ? 0 : -ENOENT;
1653 break;
1654 }
1655 ++found;
1656
1657 slot = path->slots[0];
1658 eb = path->nodes[0];
1659
1660 atomic_inc(&eb->refs);
1661
1662 btrfs_tree_read_lock(eb);
1663 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1664 btrfs_release_path(path);
1665
1666 leaf = path->nodes[0];
1667 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1668 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1669 cur_offset = 0;
1670
1671 while (cur_offset < item_size) {
1672 u32 name_len;
1673
1674 extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
1675 parent = btrfs_inode_extref_parent(eb, extref);
1676 name_len = btrfs_inode_extref_name_len(eb, extref);
1677 ret = iterate(parent, name_len,
1678 (unsigned long)&extref->name, eb, ctx);
1679 if (ret)
1680 break;
1681
1682 cur_offset += btrfs_inode_extref_name_len(leaf, extref);
1683 cur_offset += sizeof(*extref);
1684 }
1685 btrfs_tree_read_unlock_blocking(eb);
1686 free_extent_buffer(eb);
1687
1688 offset++;
1689 }
1690
1691 btrfs_release_path(path);
1692
1693 return ret;
1694}
1695
1696static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
1697 struct btrfs_path *path, iterate_irefs_t *iterate,
1698 void *ctx)
1699{
1700 int ret;
1701 int found_refs = 0;
1702
1703 ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
1704 if (!ret)
1705 ++found_refs;
1706 else if (ret != -ENOENT)
1707 return ret;
1708
1709 ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
1710 if (ret == -ENOENT && found_refs)
1711 return 0;
1712
1713 return ret;
1714}
1715
1716
1717
1718
1719
1720static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
1721 struct extent_buffer *eb, void *ctx)
1722{
1723 struct inode_fs_paths *ipath = ctx;
1724 char *fspath;
1725 char *fspath_min;
1726 int i = ipath->fspath->elem_cnt;
1727 const int s_ptr = sizeof(char *);
1728 u32 bytes_left;
1729
1730 bytes_left = ipath->fspath->bytes_left > s_ptr ?
1731 ipath->fspath->bytes_left - s_ptr : 0;
1732
1733 fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
1734 fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
1735 name_off, eb, inum, fspath_min, bytes_left);
1736 if (IS_ERR(fspath))
1737 return PTR_ERR(fspath);
1738
1739 if (fspath > fspath_min) {
1740 ipath->fspath->val[i] = (u64)(unsigned long)fspath;
1741 ++ipath->fspath->elem_cnt;
1742 ipath->fspath->bytes_left = fspath - fspath_min;
1743 } else {
1744 ++ipath->fspath->elem_missed;
1745 ipath->fspath->bytes_missing += fspath_min - fspath;
1746 ipath->fspath->bytes_left = 0;
1747 }
1748
1749 return 0;
1750}
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
1763{
1764 return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
1765 inode_to_path, ipath);
1766}
1767
1768struct btrfs_data_container *init_data_container(u32 total_bytes)
1769{
1770 struct btrfs_data_container *data;
1771 size_t alloc_bytes;
1772
1773 alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
1774 data = vmalloc(alloc_bytes);
1775 if (!data)
1776 return ERR_PTR(-ENOMEM);
1777
1778 if (total_bytes >= sizeof(*data)) {
1779 data->bytes_left = total_bytes - sizeof(*data);
1780 data->bytes_missing = 0;
1781 } else {
1782 data->bytes_missing = sizeof(*data) - total_bytes;
1783 data->bytes_left = 0;
1784 }
1785
1786 data->elem_cnt = 0;
1787 data->elem_missed = 0;
1788
1789 return data;
1790}
1791
1792
1793
1794
1795
1796
1797
1798struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
1799 struct btrfs_path *path)
1800{
1801 struct inode_fs_paths *ifp;
1802 struct btrfs_data_container *fspath;
1803
1804 fspath = init_data_container(total_bytes);
1805 if (IS_ERR(fspath))
1806 return (void *)fspath;
1807
1808 ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
1809 if (!ifp) {
1810 kfree(fspath);
1811 return ERR_PTR(-ENOMEM);
1812 }
1813
1814 ifp->btrfs_path = path;
1815 ifp->fspath = fspath;
1816 ifp->fs_root = fs_root;
1817
1818 return ifp;
1819}
1820
1821void free_ipath(struct inode_fs_paths *ipath)
1822{
1823 if (!ipath)
1824 return;
1825 vfree(ipath->fspath);
1826 kfree(ipath);
1827}
1828