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