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