1
2
3
4
5
6#include <linux/mm.h>
7#include <linux/rbtree.h>
8#include <trace/events/btrfs.h>
9#include "ctree.h"
10#include "disk-io.h"
11#include "backref.h"
12#include "ulist.h"
13#include "transaction.h"
14#include "delayed-ref.h"
15#include "locking.h"
16#include "misc.h"
17#include "tree-mod-log.h"
18
19
20#define BACKREF_FOUND_SHARED 6
21
22struct extent_inode_elem {
23 u64 inum;
24 u64 offset;
25 struct extent_inode_elem *next;
26};
27
28static int check_extent_in_eb(const struct btrfs_key *key,
29 const struct extent_buffer *eb,
30 const struct btrfs_file_extent_item *fi,
31 u64 extent_item_pos,
32 struct extent_inode_elem **eie,
33 bool ignore_offset)
34{
35 u64 offset = 0;
36 struct extent_inode_elem *e;
37
38 if (!ignore_offset &&
39 !btrfs_file_extent_compression(eb, fi) &&
40 !btrfs_file_extent_encryption(eb, fi) &&
41 !btrfs_file_extent_other_encoding(eb, fi)) {
42 u64 data_offset;
43 u64 data_len;
44
45 data_offset = btrfs_file_extent_offset(eb, fi);
46 data_len = btrfs_file_extent_num_bytes(eb, fi);
47
48 if (extent_item_pos < data_offset ||
49 extent_item_pos >= data_offset + data_len)
50 return 1;
51 offset = extent_item_pos - data_offset;
52 }
53
54 e = kmalloc(sizeof(*e), GFP_NOFS);
55 if (!e)
56 return -ENOMEM;
57
58 e->next = *eie;
59 e->inum = key->objectid;
60 e->offset = key->offset + offset;
61 *eie = e;
62
63 return 0;
64}
65
66static void free_inode_elem_list(struct extent_inode_elem *eie)
67{
68 struct extent_inode_elem *eie_next;
69
70 for (; eie; eie = eie_next) {
71 eie_next = eie->next;
72 kfree(eie);
73 }
74}
75
76static int find_extent_in_eb(const struct extent_buffer *eb,
77 u64 wanted_disk_byte, u64 extent_item_pos,
78 struct extent_inode_elem **eie,
79 bool ignore_offset)
80{
81 u64 disk_byte;
82 struct btrfs_key key;
83 struct btrfs_file_extent_item *fi;
84 int slot;
85 int nritems;
86 int extent_type;
87 int ret;
88
89
90
91
92
93
94 nritems = btrfs_header_nritems(eb);
95 for (slot = 0; slot < nritems; ++slot) {
96 btrfs_item_key_to_cpu(eb, &key, slot);
97 if (key.type != BTRFS_EXTENT_DATA_KEY)
98 continue;
99 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
100 extent_type = btrfs_file_extent_type(eb, fi);
101 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
102 continue;
103
104 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
105 if (disk_byte != wanted_disk_byte)
106 continue;
107
108 ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie, ignore_offset);
109 if (ret < 0)
110 return ret;
111 }
112
113 return 0;
114}
115
116struct preftree {
117 struct rb_root_cached root;
118 unsigned int count;
119};
120
121#define PREFTREE_INIT { .root = RB_ROOT_CACHED, .count = 0 }
122
123struct preftrees {
124 struct preftree direct;
125 struct preftree indirect;
126 struct preftree indirect_missing_keys;
127};
128
129
130
131
132
133
134
135
136
137struct share_check {
138 u64 root_objectid;
139 u64 inum;
140 int share_count;
141};
142
143static inline int extent_is_shared(struct share_check *sc)
144{
145 return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;
146}
147
148static struct kmem_cache *btrfs_prelim_ref_cache;
149
150int __init btrfs_prelim_ref_init(void)
151{
152 btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",
153 sizeof(struct prelim_ref),
154 0,
155 SLAB_MEM_SPREAD,
156 NULL);
157 if (!btrfs_prelim_ref_cache)
158 return -ENOMEM;
159 return 0;
160}
161
162void __cold btrfs_prelim_ref_exit(void)
163{
164 kmem_cache_destroy(btrfs_prelim_ref_cache);
165}
166
167static void free_pref(struct prelim_ref *ref)
168{
169 kmem_cache_free(btrfs_prelim_ref_cache, ref);
170}
171
172
173
174
175
176
177static int prelim_ref_compare(struct prelim_ref *ref1,
178 struct prelim_ref *ref2)
179{
180 if (ref1->level < ref2->level)
181 return -1;
182 if (ref1->level > ref2->level)
183 return 1;
184 if (ref1->root_id < ref2->root_id)
185 return -1;
186 if (ref1->root_id > ref2->root_id)
187 return 1;
188 if (ref1->key_for_search.type < ref2->key_for_search.type)
189 return -1;
190 if (ref1->key_for_search.type > ref2->key_for_search.type)
191 return 1;
192 if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
193 return -1;
194 if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
195 return 1;
196 if (ref1->key_for_search.offset < ref2->key_for_search.offset)
197 return -1;
198 if (ref1->key_for_search.offset > ref2->key_for_search.offset)
199 return 1;
200 if (ref1->parent < ref2->parent)
201 return -1;
202 if (ref1->parent > ref2->parent)
203 return 1;
204
205 return 0;
206}
207
208static void update_share_count(struct share_check *sc, int oldcount,
209 int newcount)
210{
211 if ((!sc) || (oldcount == 0 && newcount < 1))
212 return;
213
214 if (oldcount > 0 && newcount < 1)
215 sc->share_count--;
216 else if (oldcount < 1 && newcount > 0)
217 sc->share_count++;
218}
219
220
221
222
223
224
225static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
226 struct preftree *preftree,
227 struct prelim_ref *newref,
228 struct share_check *sc)
229{
230 struct rb_root_cached *root;
231 struct rb_node **p;
232 struct rb_node *parent = NULL;
233 struct prelim_ref *ref;
234 int result;
235 bool leftmost = true;
236
237 root = &preftree->root;
238 p = &root->rb_root.rb_node;
239
240 while (*p) {
241 parent = *p;
242 ref = rb_entry(parent, struct prelim_ref, rbnode);
243 result = prelim_ref_compare(ref, newref);
244 if (result < 0) {
245 p = &(*p)->rb_left;
246 } else if (result > 0) {
247 p = &(*p)->rb_right;
248 leftmost = false;
249 } else {
250
251 struct extent_inode_elem *eie = ref->inode_list;
252
253 while (eie && eie->next)
254 eie = eie->next;
255
256 if (!eie)
257 ref->inode_list = newref->inode_list;
258 else
259 eie->next = newref->inode_list;
260 trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
261 preftree->count);
262
263
264
265
266
267 update_share_count(sc, ref->count,
268 ref->count + newref->count);
269 ref->count += newref->count;
270 free_pref(newref);
271 return;
272 }
273 }
274
275 update_share_count(sc, 0, newref->count);
276 preftree->count++;
277 trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
278 rb_link_node(&newref->rbnode, parent, p);
279 rb_insert_color_cached(&newref->rbnode, root, leftmost);
280}
281
282
283
284
285
286static void prelim_release(struct preftree *preftree)
287{
288 struct prelim_ref *ref, *next_ref;
289
290 rbtree_postorder_for_each_entry_safe(ref, next_ref,
291 &preftree->root.rb_root, rbnode)
292 free_pref(ref);
293
294 preftree->root = RB_ROOT_CACHED;
295 preftree->count = 0;
296}
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
337 struct preftree *preftree, u64 root_id,
338 const struct btrfs_key *key, int level, u64 parent,
339 u64 wanted_disk_byte, int count,
340 struct share_check *sc, gfp_t gfp_mask)
341{
342 struct prelim_ref *ref;
343
344 if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
345 return 0;
346
347 ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);
348 if (!ref)
349 return -ENOMEM;
350
351 ref->root_id = root_id;
352 if (key)
353 ref->key_for_search = *key;
354 else
355 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
356
357 ref->inode_list = NULL;
358 ref->level = level;
359 ref->count = count;
360 ref->parent = parent;
361 ref->wanted_disk_byte = wanted_disk_byte;
362 prelim_ref_insert(fs_info, preftree, ref, sc);
363 return extent_is_shared(sc);
364}
365
366
367static int add_direct_ref(const struct btrfs_fs_info *fs_info,
368 struct preftrees *preftrees, int level, u64 parent,
369 u64 wanted_disk_byte, int count,
370 struct share_check *sc, gfp_t gfp_mask)
371{
372 return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
373 parent, wanted_disk_byte, count, sc, gfp_mask);
374}
375
376
377static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
378 struct preftrees *preftrees, u64 root_id,
379 const struct btrfs_key *key, int level,
380 u64 wanted_disk_byte, int count,
381 struct share_check *sc, gfp_t gfp_mask)
382{
383 struct preftree *tree = &preftrees->indirect;
384
385 if (!key)
386 tree = &preftrees->indirect_missing_keys;
387 return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
388 wanted_disk_byte, count, sc, gfp_mask);
389}
390
391static int is_shared_data_backref(struct preftrees *preftrees, u64 bytenr)
392{
393 struct rb_node **p = &preftrees->direct.root.rb_root.rb_node;
394 struct rb_node *parent = NULL;
395 struct prelim_ref *ref = NULL;
396 struct prelim_ref target = {};
397 int result;
398
399 target.parent = bytenr;
400
401 while (*p) {
402 parent = *p;
403 ref = rb_entry(parent, struct prelim_ref, rbnode);
404 result = prelim_ref_compare(ref, &target);
405
406 if (result < 0)
407 p = &(*p)->rb_left;
408 else if (result > 0)
409 p = &(*p)->rb_right;
410 else
411 return 1;
412 }
413 return 0;
414}
415
416static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
417 struct ulist *parents,
418 struct preftrees *preftrees, struct prelim_ref *ref,
419 int level, u64 time_seq, const u64 *extent_item_pos,
420 bool ignore_offset)
421{
422 int ret = 0;
423 int slot;
424 struct extent_buffer *eb;
425 struct btrfs_key key;
426 struct btrfs_key *key_for_search = &ref->key_for_search;
427 struct btrfs_file_extent_item *fi;
428 struct extent_inode_elem *eie = NULL, *old = NULL;
429 u64 disk_byte;
430 u64 wanted_disk_byte = ref->wanted_disk_byte;
431 u64 count = 0;
432 u64 data_offset;
433
434 if (level != 0) {
435 eb = path->nodes[level];
436 ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
437 if (ret < 0)
438 return ret;
439 return 0;
440 }
441
442
443
444
445
446
447
448
449
450
451
452 eb = path->nodes[0];
453 if (path->slots[0] >= btrfs_header_nritems(eb) ||
454 is_shared_data_backref(preftrees, eb->start) ||
455 ref->root_id != btrfs_header_owner(eb)) {
456 if (time_seq == BTRFS_SEQ_LAST)
457 ret = btrfs_next_leaf(root, path);
458 else
459 ret = btrfs_next_old_leaf(root, path, time_seq);
460 }
461
462 while (!ret && count < ref->count) {
463 eb = path->nodes[0];
464 slot = path->slots[0];
465
466 btrfs_item_key_to_cpu(eb, &key, slot);
467
468 if (key.objectid != key_for_search->objectid ||
469 key.type != BTRFS_EXTENT_DATA_KEY)
470 break;
471
472
473
474
475
476
477 if (slot == 0 &&
478 (is_shared_data_backref(preftrees, eb->start) ||
479 ref->root_id != btrfs_header_owner(eb))) {
480 if (time_seq == BTRFS_SEQ_LAST)
481 ret = btrfs_next_leaf(root, path);
482 else
483 ret = btrfs_next_old_leaf(root, path, time_seq);
484 continue;
485 }
486 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
487 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
488 data_offset = btrfs_file_extent_offset(eb, fi);
489
490 if (disk_byte == wanted_disk_byte) {
491 eie = NULL;
492 old = NULL;
493 if (ref->key_for_search.offset == key.offset - data_offset)
494 count++;
495 else
496 goto next;
497 if (extent_item_pos) {
498 ret = check_extent_in_eb(&key, eb, fi,
499 *extent_item_pos,
500 &eie, ignore_offset);
501 if (ret < 0)
502 break;
503 }
504 if (ret > 0)
505 goto next;
506 ret = ulist_add_merge_ptr(parents, eb->start,
507 eie, (void **)&old, GFP_NOFS);
508 if (ret < 0)
509 break;
510 if (!ret && extent_item_pos) {
511 while (old->next)
512 old = old->next;
513 old->next = eie;
514 }
515 eie = NULL;
516 }
517next:
518 if (time_seq == BTRFS_SEQ_LAST)
519 ret = btrfs_next_item(root, path);
520 else
521 ret = btrfs_next_old_item(root, path, time_seq);
522 }
523
524 if (ret > 0)
525 ret = 0;
526 else if (ret < 0)
527 free_inode_elem_list(eie);
528 return ret;
529}
530
531
532
533
534
535static int resolve_indirect_ref(struct btrfs_fs_info *fs_info,
536 struct btrfs_path *path, u64 time_seq,
537 struct preftrees *preftrees,
538 struct prelim_ref *ref, struct ulist *parents,
539 const u64 *extent_item_pos, bool ignore_offset)
540{
541 struct btrfs_root *root;
542 struct extent_buffer *eb;
543 int ret = 0;
544 int root_level;
545 int level = ref->level;
546 struct btrfs_key search_key = ref->key_for_search;
547
548
549
550
551
552
553
554
555
556 if (path->search_commit_root)
557 root = btrfs_get_fs_root_commit_root(fs_info, path, ref->root_id);
558 else
559 root = btrfs_get_fs_root(fs_info, ref->root_id, false);
560 if (IS_ERR(root)) {
561 ret = PTR_ERR(root);
562 goto out_free;
563 }
564
565 if (!path->search_commit_root &&
566 test_bit(BTRFS_ROOT_DELETING, &root->state)) {
567 ret = -ENOENT;
568 goto out;
569 }
570
571 if (btrfs_is_testing(fs_info)) {
572 ret = -ENOENT;
573 goto out;
574 }
575
576 if (path->search_commit_root)
577 root_level = btrfs_header_level(root->commit_root);
578 else if (time_seq == BTRFS_SEQ_LAST)
579 root_level = btrfs_header_level(root->node);
580 else
581 root_level = btrfs_old_root_level(root, time_seq);
582
583 if (root_level + 1 == level)
584 goto out;
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605 if (search_key.type == BTRFS_EXTENT_DATA_KEY &&
606 search_key.offset >= LLONG_MAX)
607 search_key.offset = 0;
608 path->lowest_level = level;
609 if (time_seq == BTRFS_SEQ_LAST)
610 ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
611 else
612 ret = btrfs_search_old_slot(root, &search_key, path, time_seq);
613
614 btrfs_debug(fs_info,
615 "search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
616 ref->root_id, level, ref->count, ret,
617 ref->key_for_search.objectid, ref->key_for_search.type,
618 ref->key_for_search.offset);
619 if (ret < 0)
620 goto out;
621
622 eb = path->nodes[level];
623 while (!eb) {
624 if (WARN_ON(!level)) {
625 ret = 1;
626 goto out;
627 }
628 level--;
629 eb = path->nodes[level];
630 }
631
632 ret = add_all_parents(root, path, parents, preftrees, ref, level,
633 time_seq, extent_item_pos, ignore_offset);
634out:
635 btrfs_put_root(root);
636out_free:
637 path->lowest_level = 0;
638 btrfs_release_path(path);
639 return ret;
640}
641
642static struct extent_inode_elem *
643unode_aux_to_inode_list(struct ulist_node *node)
644{
645 if (!node)
646 return NULL;
647 return (struct extent_inode_elem *)(uintptr_t)node->aux;
648}
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
667 struct btrfs_path *path, u64 time_seq,
668 struct preftrees *preftrees,
669 const u64 *extent_item_pos,
670 struct share_check *sc, bool ignore_offset)
671{
672 int err;
673 int ret = 0;
674 struct ulist *parents;
675 struct ulist_node *node;
676 struct ulist_iterator uiter;
677 struct rb_node *rnode;
678
679 parents = ulist_alloc(GFP_NOFS);
680 if (!parents)
681 return -ENOMEM;
682
683
684
685
686
687
688
689 while ((rnode = rb_first_cached(&preftrees->indirect.root))) {
690 struct prelim_ref *ref;
691
692 ref = rb_entry(rnode, struct prelim_ref, rbnode);
693 if (WARN(ref->parent,
694 "BUG: direct ref found in indirect tree")) {
695 ret = -EINVAL;
696 goto out;
697 }
698
699 rb_erase_cached(&ref->rbnode, &preftrees->indirect.root);
700 preftrees->indirect.count--;
701
702 if (ref->count == 0) {
703 free_pref(ref);
704 continue;
705 }
706
707 if (sc && sc->root_objectid &&
708 ref->root_id != sc->root_objectid) {
709 free_pref(ref);
710 ret = BACKREF_FOUND_SHARED;
711 goto out;
712 }
713 err = resolve_indirect_ref(fs_info, path, time_seq, preftrees,
714 ref, parents, extent_item_pos,
715 ignore_offset);
716
717
718
719
720 if (err == -ENOENT) {
721 prelim_ref_insert(fs_info, &preftrees->direct, ref,
722 NULL);
723 continue;
724 } else if (err) {
725 free_pref(ref);
726 ret = err;
727 goto out;
728 }
729
730
731 ULIST_ITER_INIT(&uiter);
732 node = ulist_next(parents, &uiter);
733 ref->parent = node ? node->val : 0;
734 ref->inode_list = unode_aux_to_inode_list(node);
735
736
737 while ((node = ulist_next(parents, &uiter))) {
738 struct prelim_ref *new_ref;
739
740 new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
741 GFP_NOFS);
742 if (!new_ref) {
743 free_pref(ref);
744 ret = -ENOMEM;
745 goto out;
746 }
747 memcpy(new_ref, ref, sizeof(*ref));
748 new_ref->parent = node->val;
749 new_ref->inode_list = unode_aux_to_inode_list(node);
750 prelim_ref_insert(fs_info, &preftrees->direct,
751 new_ref, NULL);
752 }
753
754
755
756
757
758 prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL);
759
760 ulist_reinit(parents);
761 cond_resched();
762 }
763out:
764 ulist_free(parents);
765 return ret;
766}
767
768
769
770
771static int add_missing_keys(struct btrfs_fs_info *fs_info,
772 struct preftrees *preftrees, bool lock)
773{
774 struct prelim_ref *ref;
775 struct extent_buffer *eb;
776 struct preftree *tree = &preftrees->indirect_missing_keys;
777 struct rb_node *node;
778
779 while ((node = rb_first_cached(&tree->root))) {
780 ref = rb_entry(node, struct prelim_ref, rbnode);
781 rb_erase_cached(node, &tree->root);
782
783 BUG_ON(ref->parent);
784 BUG_ON(ref->key_for_search.type);
785 BUG_ON(!ref->wanted_disk_byte);
786
787 eb = read_tree_block(fs_info, ref->wanted_disk_byte,
788 ref->root_id, 0, ref->level - 1, NULL);
789 if (IS_ERR(eb)) {
790 free_pref(ref);
791 return PTR_ERR(eb);
792 } else if (!extent_buffer_uptodate(eb)) {
793 free_pref(ref);
794 free_extent_buffer(eb);
795 return -EIO;
796 }
797 if (lock)
798 btrfs_tree_read_lock(eb);
799 if (btrfs_header_level(eb) == 0)
800 btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
801 else
802 btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
803 if (lock)
804 btrfs_tree_read_unlock(eb);
805 free_extent_buffer(eb);
806 prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);
807 cond_resched();
808 }
809 return 0;
810}
811
812
813
814
815
816static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
817 struct btrfs_delayed_ref_head *head, u64 seq,
818 struct preftrees *preftrees, struct share_check *sc)
819{
820 struct btrfs_delayed_ref_node *node;
821 struct btrfs_delayed_extent_op *extent_op = head->extent_op;
822 struct btrfs_key key;
823 struct btrfs_key tmp_op_key;
824 struct rb_node *n;
825 int count;
826 int ret = 0;
827
828 if (extent_op && extent_op->update_key)
829 btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key);
830
831 spin_lock(&head->lock);
832 for (n = rb_first_cached(&head->ref_tree); n; n = rb_next(n)) {
833 node = rb_entry(n, struct btrfs_delayed_ref_node,
834 ref_node);
835 if (node->seq > seq)
836 continue;
837
838 switch (node->action) {
839 case BTRFS_ADD_DELAYED_EXTENT:
840 case BTRFS_UPDATE_DELAYED_HEAD:
841 WARN_ON(1);
842 continue;
843 case BTRFS_ADD_DELAYED_REF:
844 count = node->ref_mod;
845 break;
846 case BTRFS_DROP_DELAYED_REF:
847 count = node->ref_mod * -1;
848 break;
849 default:
850 BUG();
851 }
852 switch (node->type) {
853 case BTRFS_TREE_BLOCK_REF_KEY: {
854
855 struct btrfs_delayed_tree_ref *ref;
856
857 ref = btrfs_delayed_node_to_tree_ref(node);
858 ret = add_indirect_ref(fs_info, preftrees, ref->root,
859 &tmp_op_key, ref->level + 1,
860 node->bytenr, count, sc,
861 GFP_ATOMIC);
862 break;
863 }
864 case BTRFS_SHARED_BLOCK_REF_KEY: {
865
866 struct btrfs_delayed_tree_ref *ref;
867
868 ref = btrfs_delayed_node_to_tree_ref(node);
869
870 ret = add_direct_ref(fs_info, preftrees, ref->level + 1,
871 ref->parent, node->bytenr, count,
872 sc, GFP_ATOMIC);
873 break;
874 }
875 case BTRFS_EXTENT_DATA_REF_KEY: {
876
877 struct btrfs_delayed_data_ref *ref;
878 ref = btrfs_delayed_node_to_data_ref(node);
879
880 key.objectid = ref->objectid;
881 key.type = BTRFS_EXTENT_DATA_KEY;
882 key.offset = ref->offset;
883
884
885
886
887
888 if (sc && sc->inum && ref->objectid != sc->inum) {
889 ret = BACKREF_FOUND_SHARED;
890 goto out;
891 }
892
893 ret = add_indirect_ref(fs_info, preftrees, ref->root,
894 &key, 0, node->bytenr, count, sc,
895 GFP_ATOMIC);
896 break;
897 }
898 case BTRFS_SHARED_DATA_REF_KEY: {
899
900 struct btrfs_delayed_data_ref *ref;
901
902 ref = btrfs_delayed_node_to_data_ref(node);
903
904 ret = add_direct_ref(fs_info, preftrees, 0, ref->parent,
905 node->bytenr, count, sc,
906 GFP_ATOMIC);
907 break;
908 }
909 default:
910 WARN_ON(1);
911 }
912
913
914
915
916 if (ret && (ret != BACKREF_FOUND_SHARED))
917 break;
918 }
919 if (!ret)
920 ret = extent_is_shared(sc);
921out:
922 spin_unlock(&head->lock);
923 return ret;
924}
925
926
927
928
929
930
931static int add_inline_refs(const struct btrfs_fs_info *fs_info,
932 struct btrfs_path *path, u64 bytenr,
933 int *info_level, struct preftrees *preftrees,
934 struct share_check *sc)
935{
936 int ret = 0;
937 int slot;
938 struct extent_buffer *leaf;
939 struct btrfs_key key;
940 struct btrfs_key found_key;
941 unsigned long ptr;
942 unsigned long end;
943 struct btrfs_extent_item *ei;
944 u64 flags;
945 u64 item_size;
946
947
948
949
950 leaf = path->nodes[0];
951 slot = path->slots[0];
952
953 item_size = btrfs_item_size_nr(leaf, slot);
954 BUG_ON(item_size < sizeof(*ei));
955
956 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
957 flags = btrfs_extent_flags(leaf, ei);
958 btrfs_item_key_to_cpu(leaf, &found_key, slot);
959
960 ptr = (unsigned long)(ei + 1);
961 end = (unsigned long)ei + item_size;
962
963 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
964 flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
965 struct btrfs_tree_block_info *info;
966
967 info = (struct btrfs_tree_block_info *)ptr;
968 *info_level = btrfs_tree_block_level(leaf, info);
969 ptr += sizeof(struct btrfs_tree_block_info);
970 BUG_ON(ptr > end);
971 } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
972 *info_level = found_key.offset;
973 } else {
974 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
975 }
976
977 while (ptr < end) {
978 struct btrfs_extent_inline_ref *iref;
979 u64 offset;
980 int type;
981
982 iref = (struct btrfs_extent_inline_ref *)ptr;
983 type = btrfs_get_extent_inline_ref_type(leaf, iref,
984 BTRFS_REF_TYPE_ANY);
985 if (type == BTRFS_REF_TYPE_INVALID)
986 return -EUCLEAN;
987
988 offset = btrfs_extent_inline_ref_offset(leaf, iref);
989
990 switch (type) {
991 case BTRFS_SHARED_BLOCK_REF_KEY:
992 ret = add_direct_ref(fs_info, preftrees,
993 *info_level + 1, offset,
994 bytenr, 1, NULL, GFP_NOFS);
995 break;
996 case BTRFS_SHARED_DATA_REF_KEY: {
997 struct btrfs_shared_data_ref *sdref;
998 int count;
999
1000 sdref = (struct btrfs_shared_data_ref *)(iref + 1);
1001 count = btrfs_shared_data_ref_count(leaf, sdref);
1002
1003 ret = add_direct_ref(fs_info, preftrees, 0, offset,
1004 bytenr, count, sc, GFP_NOFS);
1005 break;
1006 }
1007 case BTRFS_TREE_BLOCK_REF_KEY:
1008 ret = add_indirect_ref(fs_info, preftrees, offset,
1009 NULL, *info_level + 1,
1010 bytenr, 1, NULL, GFP_NOFS);
1011 break;
1012 case BTRFS_EXTENT_DATA_REF_KEY: {
1013 struct btrfs_extent_data_ref *dref;
1014 int count;
1015 u64 root;
1016
1017 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1018 count = btrfs_extent_data_ref_count(leaf, dref);
1019 key.objectid = btrfs_extent_data_ref_objectid(leaf,
1020 dref);
1021 key.type = BTRFS_EXTENT_DATA_KEY;
1022 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1023
1024 if (sc && sc->inum && key.objectid != sc->inum) {
1025 ret = BACKREF_FOUND_SHARED;
1026 break;
1027 }
1028
1029 root = btrfs_extent_data_ref_root(leaf, dref);
1030
1031 ret = add_indirect_ref(fs_info, preftrees, root,
1032 &key, 0, bytenr, count,
1033 sc, GFP_NOFS);
1034 break;
1035 }
1036 default:
1037 WARN_ON(1);
1038 }
1039 if (ret)
1040 return ret;
1041 ptr += btrfs_extent_inline_ref_size(type);
1042 }
1043
1044 return 0;
1045}
1046
1047
1048
1049
1050
1051
1052static int add_keyed_refs(struct btrfs_fs_info *fs_info,
1053 struct btrfs_path *path, u64 bytenr,
1054 int info_level, struct preftrees *preftrees,
1055 struct share_check *sc)
1056{
1057 struct btrfs_root *extent_root = fs_info->extent_root;
1058 int ret;
1059 int slot;
1060 struct extent_buffer *leaf;
1061 struct btrfs_key key;
1062
1063 while (1) {
1064 ret = btrfs_next_item(extent_root, path);
1065 if (ret < 0)
1066 break;
1067 if (ret) {
1068 ret = 0;
1069 break;
1070 }
1071
1072 slot = path->slots[0];
1073 leaf = path->nodes[0];
1074 btrfs_item_key_to_cpu(leaf, &key, slot);
1075
1076 if (key.objectid != bytenr)
1077 break;
1078 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
1079 continue;
1080 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
1081 break;
1082
1083 switch (key.type) {
1084 case BTRFS_SHARED_BLOCK_REF_KEY:
1085
1086 ret = add_direct_ref(fs_info, preftrees,
1087 info_level + 1, key.offset,
1088 bytenr, 1, NULL, GFP_NOFS);
1089 break;
1090 case BTRFS_SHARED_DATA_REF_KEY: {
1091
1092 struct btrfs_shared_data_ref *sdref;
1093 int count;
1094
1095 sdref = btrfs_item_ptr(leaf, slot,
1096 struct btrfs_shared_data_ref);
1097 count = btrfs_shared_data_ref_count(leaf, sdref);
1098 ret = add_direct_ref(fs_info, preftrees, 0,
1099 key.offset, bytenr, count,
1100 sc, GFP_NOFS);
1101 break;
1102 }
1103 case BTRFS_TREE_BLOCK_REF_KEY:
1104
1105 ret = add_indirect_ref(fs_info, preftrees, key.offset,
1106 NULL, info_level + 1, bytenr,
1107 1, NULL, GFP_NOFS);
1108 break;
1109 case BTRFS_EXTENT_DATA_REF_KEY: {
1110
1111 struct btrfs_extent_data_ref *dref;
1112 int count;
1113 u64 root;
1114
1115 dref = btrfs_item_ptr(leaf, slot,
1116 struct btrfs_extent_data_ref);
1117 count = btrfs_extent_data_ref_count(leaf, dref);
1118 key.objectid = btrfs_extent_data_ref_objectid(leaf,
1119 dref);
1120 key.type = BTRFS_EXTENT_DATA_KEY;
1121 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1122
1123 if (sc && sc->inum && key.objectid != sc->inum) {
1124 ret = BACKREF_FOUND_SHARED;
1125 break;
1126 }
1127
1128 root = btrfs_extent_data_ref_root(leaf, dref);
1129 ret = add_indirect_ref(fs_info, preftrees, root,
1130 &key, 0, bytenr, count,
1131 sc, GFP_NOFS);
1132 break;
1133 }
1134 default:
1135 WARN_ON(1);
1136 }
1137 if (ret)
1138 return ret;
1139
1140 }
1141
1142 return ret;
1143}
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167static int find_parent_nodes(struct btrfs_trans_handle *trans,
1168 struct btrfs_fs_info *fs_info, u64 bytenr,
1169 u64 time_seq, struct ulist *refs,
1170 struct ulist *roots, const u64 *extent_item_pos,
1171 struct share_check *sc, bool ignore_offset)
1172{
1173 struct btrfs_key key;
1174 struct btrfs_path *path;
1175 struct btrfs_delayed_ref_root *delayed_refs = NULL;
1176 struct btrfs_delayed_ref_head *head;
1177 int info_level = 0;
1178 int ret;
1179 struct prelim_ref *ref;
1180 struct rb_node *node;
1181 struct extent_inode_elem *eie = NULL;
1182 struct preftrees preftrees = {
1183 .direct = PREFTREE_INIT,
1184 .indirect = PREFTREE_INIT,
1185 .indirect_missing_keys = PREFTREE_INIT
1186 };
1187
1188 key.objectid = bytenr;
1189 key.offset = (u64)-1;
1190 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1191 key.type = BTRFS_METADATA_ITEM_KEY;
1192 else
1193 key.type = BTRFS_EXTENT_ITEM_KEY;
1194
1195 path = btrfs_alloc_path();
1196 if (!path)
1197 return -ENOMEM;
1198 if (!trans) {
1199 path->search_commit_root = 1;
1200 path->skip_locking = 1;
1201 }
1202
1203 if (time_seq == BTRFS_SEQ_LAST)
1204 path->skip_locking = 1;
1205
1206
1207
1208
1209
1210
1211again:
1212 head = NULL;
1213
1214 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
1215 if (ret < 0)
1216 goto out;
1217 BUG_ON(ret == 0);
1218
1219#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1220 if (trans && likely(trans->type != __TRANS_DUMMY) &&
1221 time_seq != BTRFS_SEQ_LAST) {
1222#else
1223 if (trans && time_seq != BTRFS_SEQ_LAST) {
1224#endif
1225
1226
1227
1228
1229 delayed_refs = &trans->transaction->delayed_refs;
1230 spin_lock(&delayed_refs->lock);
1231 head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
1232 if (head) {
1233 if (!mutex_trylock(&head->mutex)) {
1234 refcount_inc(&head->refs);
1235 spin_unlock(&delayed_refs->lock);
1236
1237 btrfs_release_path(path);
1238
1239
1240
1241
1242
1243 mutex_lock(&head->mutex);
1244 mutex_unlock(&head->mutex);
1245 btrfs_put_delayed_ref_head(head);
1246 goto again;
1247 }
1248 spin_unlock(&delayed_refs->lock);
1249 ret = add_delayed_refs(fs_info, head, time_seq,
1250 &preftrees, sc);
1251 mutex_unlock(&head->mutex);
1252 if (ret)
1253 goto out;
1254 } else {
1255 spin_unlock(&delayed_refs->lock);
1256 }
1257 }
1258
1259 if (path->slots[0]) {
1260 struct extent_buffer *leaf;
1261 int slot;
1262
1263 path->slots[0]--;
1264 leaf = path->nodes[0];
1265 slot = path->slots[0];
1266 btrfs_item_key_to_cpu(leaf, &key, slot);
1267 if (key.objectid == bytenr &&
1268 (key.type == BTRFS_EXTENT_ITEM_KEY ||
1269 key.type == BTRFS_METADATA_ITEM_KEY)) {
1270 ret = add_inline_refs(fs_info, path, bytenr,
1271 &info_level, &preftrees, sc);
1272 if (ret)
1273 goto out;
1274 ret = add_keyed_refs(fs_info, path, bytenr, info_level,
1275 &preftrees, sc);
1276 if (ret)
1277 goto out;
1278 }
1279 }
1280
1281 btrfs_release_path(path);
1282
1283 ret = add_missing_keys(fs_info, &preftrees, path->skip_locking == 0);
1284 if (ret)
1285 goto out;
1286
1287 WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root.rb_root));
1288
1289 ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
1290 extent_item_pos, sc, ignore_offset);
1291 if (ret)
1292 goto out;
1293
1294 WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root.rb_root));
1295
1296
1297
1298
1299
1300
1301
1302
1303 node = rb_first_cached(&preftrees.direct.root);
1304 while (node) {
1305 ref = rb_entry(node, struct prelim_ref, rbnode);
1306 node = rb_next(&ref->rbnode);
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317 if (roots && ref->count && ref->root_id && ref->parent == 0) {
1318 if (sc && sc->root_objectid &&
1319 ref->root_id != sc->root_objectid) {
1320 ret = BACKREF_FOUND_SHARED;
1321 goto out;
1322 }
1323
1324
1325 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
1326 if (ret < 0)
1327 goto out;
1328 }
1329 if (ref->count && ref->parent) {
1330 if (extent_item_pos && !ref->inode_list &&
1331 ref->level == 0) {
1332 struct extent_buffer *eb;
1333
1334 eb = read_tree_block(fs_info, ref->parent, 0,
1335 0, ref->level, NULL);
1336 if (IS_ERR(eb)) {
1337 ret = PTR_ERR(eb);
1338 goto out;
1339 } else if (!extent_buffer_uptodate(eb)) {
1340 free_extent_buffer(eb);
1341 ret = -EIO;
1342 goto out;
1343 }
1344
1345 if (!path->skip_locking)
1346 btrfs_tree_read_lock(eb);
1347 ret = find_extent_in_eb(eb, bytenr,
1348 *extent_item_pos, &eie, ignore_offset);
1349 if (!path->skip_locking)
1350 btrfs_tree_read_unlock(eb);
1351 free_extent_buffer(eb);
1352 if (ret < 0)
1353 goto out;
1354 ref->inode_list = eie;
1355 }
1356 ret = ulist_add_merge_ptr(refs, ref->parent,
1357 ref->inode_list,
1358 (void **)&eie, GFP_NOFS);
1359 if (ret < 0)
1360 goto out;
1361 if (!ret && extent_item_pos) {
1362
1363
1364
1365
1366 BUG_ON(!eie);
1367 while (eie->next)
1368 eie = eie->next;
1369 eie->next = ref->inode_list;
1370 }
1371 eie = NULL;
1372 }
1373 cond_resched();
1374 }
1375
1376out:
1377 btrfs_free_path(path);
1378
1379 prelim_release(&preftrees.direct);
1380 prelim_release(&preftrees.indirect);
1381 prelim_release(&preftrees.indirect_missing_keys);
1382
1383 if (ret < 0)
1384 free_inode_elem_list(eie);
1385 return ret;
1386}
1387
1388static void free_leaf_list(struct ulist *blocks)
1389{
1390 struct ulist_node *node = NULL;
1391 struct extent_inode_elem *eie;
1392 struct ulist_iterator uiter;
1393
1394 ULIST_ITER_INIT(&uiter);
1395 while ((node = ulist_next(blocks, &uiter))) {
1396 if (!node->aux)
1397 continue;
1398 eie = unode_aux_to_inode_list(node);
1399 free_inode_elem_list(eie);
1400 node->aux = 0;
1401 }
1402
1403 ulist_free(blocks);
1404}
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
1415 struct btrfs_fs_info *fs_info, u64 bytenr,
1416 u64 time_seq, struct ulist **leafs,
1417 const u64 *extent_item_pos, bool ignore_offset)
1418{
1419 int ret;
1420
1421 *leafs = ulist_alloc(GFP_NOFS);
1422 if (!*leafs)
1423 return -ENOMEM;
1424
1425 ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1426 *leafs, NULL, extent_item_pos, NULL, ignore_offset);
1427 if (ret < 0 && ret != -ENOENT) {
1428 free_leaf_list(*leafs);
1429 return ret;
1430 }
1431
1432 return 0;
1433}
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
1449 struct btrfs_fs_info *fs_info, u64 bytenr,
1450 u64 time_seq, struct ulist **roots,
1451 bool ignore_offset)
1452{
1453 struct ulist *tmp;
1454 struct ulist_node *node = NULL;
1455 struct ulist_iterator uiter;
1456 int ret;
1457
1458 tmp = ulist_alloc(GFP_NOFS);
1459 if (!tmp)
1460 return -ENOMEM;
1461 *roots = ulist_alloc(GFP_NOFS);
1462 if (!*roots) {
1463 ulist_free(tmp);
1464 return -ENOMEM;
1465 }
1466
1467 ULIST_ITER_INIT(&uiter);
1468 while (1) {
1469 ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1470 tmp, *roots, NULL, NULL, ignore_offset);
1471 if (ret < 0 && ret != -ENOENT) {
1472 ulist_free(tmp);
1473 ulist_free(*roots);
1474 *roots = NULL;
1475 return ret;
1476 }
1477 node = ulist_next(tmp, &uiter);
1478 if (!node)
1479 break;
1480 bytenr = node->val;
1481 cond_resched();
1482 }
1483
1484 ulist_free(tmp);
1485 return 0;
1486}
1487
1488int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
1489 struct btrfs_fs_info *fs_info, u64 bytenr,
1490 u64 time_seq, struct ulist **roots,
1491 bool ignore_offset, bool skip_commit_root_sem)
1492{
1493 int ret;
1494
1495 if (!trans && !skip_commit_root_sem)
1496 down_read(&fs_info->commit_root_sem);
1497 ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr,
1498 time_seq, roots, ignore_offset);
1499 if (!trans && !skip_commit_root_sem)
1500 up_read(&fs_info->commit_root_sem);
1501 return ret;
1502}
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr,
1525 struct ulist *roots, struct ulist *tmp)
1526{
1527 struct btrfs_fs_info *fs_info = root->fs_info;
1528 struct btrfs_trans_handle *trans;
1529 struct ulist_iterator uiter;
1530 struct ulist_node *node;
1531 struct btrfs_seq_list elem = BTRFS_SEQ_LIST_INIT(elem);
1532 int ret = 0;
1533 struct share_check shared = {
1534 .root_objectid = root->root_key.objectid,
1535 .inum = inum,
1536 .share_count = 0,
1537 };
1538
1539 ulist_init(roots);
1540 ulist_init(tmp);
1541
1542 trans = btrfs_join_transaction_nostart(root);
1543 if (IS_ERR(trans)) {
1544 if (PTR_ERR(trans) != -ENOENT && PTR_ERR(trans) != -EROFS) {
1545 ret = PTR_ERR(trans);
1546 goto out;
1547 }
1548 trans = NULL;
1549 down_read(&fs_info->commit_root_sem);
1550 } else {
1551 btrfs_get_tree_mod_seq(fs_info, &elem);
1552 }
1553
1554 ULIST_ITER_INIT(&uiter);
1555 while (1) {
1556 ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
1557 roots, NULL, &shared, false);
1558 if (ret == BACKREF_FOUND_SHARED) {
1559
1560 ret = 1;
1561 break;
1562 }
1563 if (ret < 0 && ret != -ENOENT)
1564 break;
1565 ret = 0;
1566 node = ulist_next(tmp, &uiter);
1567 if (!node)
1568 break;
1569 bytenr = node->val;
1570 shared.share_count = 0;
1571 cond_resched();
1572 }
1573
1574 if (trans) {
1575 btrfs_put_tree_mod_seq(fs_info, &elem);
1576 btrfs_end_transaction(trans);
1577 } else {
1578 up_read(&fs_info->commit_root_sem);
1579 }
1580out:
1581 ulist_release(roots);
1582 ulist_release(tmp);
1583 return ret;
1584}
1585
1586int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
1587 u64 start_off, struct btrfs_path *path,
1588 struct btrfs_inode_extref **ret_extref,
1589 u64 *found_off)
1590{
1591 int ret, slot;
1592 struct btrfs_key key;
1593 struct btrfs_key found_key;
1594 struct btrfs_inode_extref *extref;
1595 const struct extent_buffer *leaf;
1596 unsigned long ptr;
1597
1598 key.objectid = inode_objectid;
1599 key.type = BTRFS_INODE_EXTREF_KEY;
1600 key.offset = start_off;
1601
1602 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1603 if (ret < 0)
1604 return ret;
1605
1606 while (1) {
1607 leaf = path->nodes[0];
1608 slot = path->slots[0];
1609 if (slot >= btrfs_header_nritems(leaf)) {
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619 ret = btrfs_next_leaf(root, path);
1620 if (ret) {
1621 if (ret >= 1)
1622 ret = -ENOENT;
1623 break;
1624 }
1625 continue;
1626 }
1627
1628 btrfs_item_key_to_cpu(leaf, &found_key, slot);
1629
1630
1631
1632
1633
1634
1635
1636 ret = -ENOENT;
1637 if (found_key.objectid != inode_objectid)
1638 break;
1639 if (found_key.type != BTRFS_INODE_EXTREF_KEY)
1640 break;
1641
1642 ret = 0;
1643 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1644 extref = (struct btrfs_inode_extref *)ptr;
1645 *ret_extref = extref;
1646 if (found_off)
1647 *found_off = found_key.offset;
1648 break;
1649 }
1650
1651 return ret;
1652}
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
1669 u32 name_len, unsigned long name_off,
1670 struct extent_buffer *eb_in, u64 parent,
1671 char *dest, u32 size)
1672{
1673 int slot;
1674 u64 next_inum;
1675 int ret;
1676 s64 bytes_left = ((s64)size) - 1;
1677 struct extent_buffer *eb = eb_in;
1678 struct btrfs_key found_key;
1679 struct btrfs_inode_ref *iref;
1680
1681 if (bytes_left >= 0)
1682 dest[bytes_left] = '\0';
1683
1684 while (1) {
1685 bytes_left -= name_len;
1686 if (bytes_left >= 0)
1687 read_extent_buffer(eb, dest + bytes_left,
1688 name_off, name_len);
1689 if (eb != eb_in) {
1690 if (!path->skip_locking)
1691 btrfs_tree_read_unlock(eb);
1692 free_extent_buffer(eb);
1693 }
1694 ret = btrfs_find_item(fs_root, path, parent, 0,
1695 BTRFS_INODE_REF_KEY, &found_key);
1696 if (ret > 0)
1697 ret = -ENOENT;
1698 if (ret)
1699 break;
1700
1701 next_inum = found_key.offset;
1702
1703
1704 if (parent == next_inum)
1705 break;
1706
1707 slot = path->slots[0];
1708 eb = path->nodes[0];
1709
1710 if (eb != eb_in) {
1711 path->nodes[0] = NULL;
1712 path->locks[0] = 0;
1713 }
1714 btrfs_release_path(path);
1715 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1716
1717 name_len = btrfs_inode_ref_name_len(eb, iref);
1718 name_off = (unsigned long)(iref + 1);
1719
1720 parent = next_inum;
1721 --bytes_left;
1722 if (bytes_left >= 0)
1723 dest[bytes_left] = '/';
1724 }
1725
1726 btrfs_release_path(path);
1727
1728 if (ret)
1729 return ERR_PTR(ret);
1730
1731 return dest + bytes_left;
1732}
1733
1734
1735
1736
1737
1738
1739int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1740 struct btrfs_path *path, struct btrfs_key *found_key,
1741 u64 *flags_ret)
1742{
1743 int ret;
1744 u64 flags;
1745 u64 size = 0;
1746 u32 item_size;
1747 const struct extent_buffer *eb;
1748 struct btrfs_extent_item *ei;
1749 struct btrfs_key key;
1750
1751 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1752 key.type = BTRFS_METADATA_ITEM_KEY;
1753 else
1754 key.type = BTRFS_EXTENT_ITEM_KEY;
1755 key.objectid = logical;
1756 key.offset = (u64)-1;
1757
1758 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1759 if (ret < 0)
1760 return ret;
1761
1762 ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
1763 if (ret) {
1764 if (ret > 0)
1765 ret = -ENOENT;
1766 return ret;
1767 }
1768 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1769 if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1770 size = fs_info->nodesize;
1771 else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
1772 size = found_key->offset;
1773
1774 if (found_key->objectid > logical ||
1775 found_key->objectid + size <= logical) {
1776 btrfs_debug(fs_info,
1777 "logical %llu is not within any extent", logical);
1778 return -ENOENT;
1779 }
1780
1781 eb = path->nodes[0];
1782 item_size = btrfs_item_size_nr(eb, path->slots[0]);
1783 BUG_ON(item_size < sizeof(*ei));
1784
1785 ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
1786 flags = btrfs_extent_flags(eb, ei);
1787
1788 btrfs_debug(fs_info,
1789 "logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u",
1790 logical, logical - found_key->objectid, found_key->objectid,
1791 found_key->offset, flags, item_size);
1792
1793 WARN_ON(!flags_ret);
1794 if (flags_ret) {
1795 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1796 *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
1797 else if (flags & BTRFS_EXTENT_FLAG_DATA)
1798 *flags_ret = BTRFS_EXTENT_FLAG_DATA;
1799 else
1800 BUG();
1801 return 0;
1802 }
1803
1804 return -EIO;
1805}
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815static int get_extent_inline_ref(unsigned long *ptr,
1816 const struct extent_buffer *eb,
1817 const struct btrfs_key *key,
1818 const struct btrfs_extent_item *ei,
1819 u32 item_size,
1820 struct btrfs_extent_inline_ref **out_eiref,
1821 int *out_type)
1822{
1823 unsigned long end;
1824 u64 flags;
1825 struct btrfs_tree_block_info *info;
1826
1827 if (!*ptr) {
1828
1829 flags = btrfs_extent_flags(eb, ei);
1830 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1831 if (key->type == BTRFS_METADATA_ITEM_KEY) {
1832
1833 *out_eiref =
1834 (struct btrfs_extent_inline_ref *)(ei + 1);
1835 } else {
1836 WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);
1837 info = (struct btrfs_tree_block_info *)(ei + 1);
1838 *out_eiref =
1839 (struct btrfs_extent_inline_ref *)(info + 1);
1840 }
1841 } else {
1842 *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
1843 }
1844 *ptr = (unsigned long)*out_eiref;
1845 if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
1846 return -ENOENT;
1847 }
1848
1849 end = (unsigned long)ei + item_size;
1850 *out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
1851 *out_type = btrfs_get_extent_inline_ref_type(eb, *out_eiref,
1852 BTRFS_REF_TYPE_ANY);
1853 if (*out_type == BTRFS_REF_TYPE_INVALID)
1854 return -EUCLEAN;
1855
1856 *ptr += btrfs_extent_inline_ref_size(*out_type);
1857 WARN_ON(*ptr > end);
1858 if (*ptr == end)
1859 return 1;
1860
1861 return 0;
1862}
1863
1864
1865
1866
1867
1868
1869
1870
1871int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
1872 struct btrfs_key *key, struct btrfs_extent_item *ei,
1873 u32 item_size, u64 *out_root, u8 *out_level)
1874{
1875 int ret;
1876 int type;
1877 struct btrfs_extent_inline_ref *eiref;
1878
1879 if (*ptr == (unsigned long)-1)
1880 return 1;
1881
1882 while (1) {
1883 ret = get_extent_inline_ref(ptr, eb, key, ei, item_size,
1884 &eiref, &type);
1885 if (ret < 0)
1886 return ret;
1887
1888 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1889 type == BTRFS_SHARED_BLOCK_REF_KEY)
1890 break;
1891
1892 if (ret == 1)
1893 return 1;
1894 }
1895
1896
1897 *out_root = btrfs_extent_inline_ref_offset(eb, eiref);
1898
1899 if (key->type == BTRFS_EXTENT_ITEM_KEY) {
1900 struct btrfs_tree_block_info *info;
1901
1902 info = (struct btrfs_tree_block_info *)(ei + 1);
1903 *out_level = btrfs_tree_block_level(eb, info);
1904 } else {
1905 ASSERT(key->type == BTRFS_METADATA_ITEM_KEY);
1906 *out_level = (u8)key->offset;
1907 }
1908
1909 if (ret == 1)
1910 *ptr = (unsigned long)-1;
1911
1912 return 0;
1913}
1914
1915static int iterate_leaf_refs(struct btrfs_fs_info *fs_info,
1916 struct extent_inode_elem *inode_list,
1917 u64 root, u64 extent_item_objectid,
1918 iterate_extent_inodes_t *iterate, void *ctx)
1919{
1920 struct extent_inode_elem *eie;
1921 int ret = 0;
1922
1923 for (eie = inode_list; eie; eie = eie->next) {
1924 btrfs_debug(fs_info,
1925 "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",
1926 extent_item_objectid, eie->inum,
1927 eie->offset, root);
1928 ret = iterate(eie->inum, eie->offset, root, ctx);
1929 if (ret) {
1930 btrfs_debug(fs_info,
1931 "stopping iteration for %llu due to ret=%d",
1932 extent_item_objectid, ret);
1933 break;
1934 }
1935 }
1936
1937 return ret;
1938}
1939
1940
1941
1942
1943
1944
1945int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
1946 u64 extent_item_objectid, u64 extent_item_pos,
1947 int search_commit_root,
1948 iterate_extent_inodes_t *iterate, void *ctx,
1949 bool ignore_offset)
1950{
1951 int ret;
1952 struct btrfs_trans_handle *trans = NULL;
1953 struct ulist *refs = NULL;
1954 struct ulist *roots = NULL;
1955 struct ulist_node *ref_node = NULL;
1956 struct ulist_node *root_node = NULL;
1957 struct btrfs_seq_list seq_elem = BTRFS_SEQ_LIST_INIT(seq_elem);
1958 struct ulist_iterator ref_uiter;
1959 struct ulist_iterator root_uiter;
1960
1961 btrfs_debug(fs_info, "resolving all inodes for extent %llu",
1962 extent_item_objectid);
1963
1964 if (!search_commit_root) {
1965 trans = btrfs_attach_transaction(fs_info->extent_root);
1966 if (IS_ERR(trans)) {
1967 if (PTR_ERR(trans) != -ENOENT &&
1968 PTR_ERR(trans) != -EROFS)
1969 return PTR_ERR(trans);
1970 trans = NULL;
1971 }
1972 }
1973
1974 if (trans)
1975 btrfs_get_tree_mod_seq(fs_info, &seq_elem);
1976 else
1977 down_read(&fs_info->commit_root_sem);
1978
1979 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1980 seq_elem.seq, &refs,
1981 &extent_item_pos, ignore_offset);
1982 if (ret)
1983 goto out;
1984
1985 ULIST_ITER_INIT(&ref_uiter);
1986 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1987 ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val,
1988 seq_elem.seq, &roots,
1989 ignore_offset);
1990 if (ret)
1991 break;
1992 ULIST_ITER_INIT(&root_uiter);
1993 while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1994 btrfs_debug(fs_info,
1995 "root %llu references leaf %llu, data list %#llx",
1996 root_node->val, ref_node->val,
1997 ref_node->aux);
1998 ret = iterate_leaf_refs(fs_info,
1999 (struct extent_inode_elem *)
2000 (uintptr_t)ref_node->aux,
2001 root_node->val,
2002 extent_item_objectid,
2003 iterate, ctx);
2004 }
2005 ulist_free(roots);
2006 }
2007
2008 free_leaf_list(refs);
2009out:
2010 if (trans) {
2011 btrfs_put_tree_mod_seq(fs_info, &seq_elem);
2012 btrfs_end_transaction(trans);
2013 } else {
2014 up_read(&fs_info->commit_root_sem);
2015 }
2016
2017 return ret;
2018}
2019
2020int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
2021 struct btrfs_path *path,
2022 iterate_extent_inodes_t *iterate, void *ctx,
2023 bool ignore_offset)
2024{
2025 int ret;
2026 u64 extent_item_pos;
2027 u64 flags = 0;
2028 struct btrfs_key found_key;
2029 int search_commit_root = path->search_commit_root;
2030
2031 ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
2032 btrfs_release_path(path);
2033 if (ret < 0)
2034 return ret;
2035 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2036 return -EINVAL;
2037
2038 extent_item_pos = logical - found_key.objectid;
2039 ret = iterate_extent_inodes(fs_info, found_key.objectid,
2040 extent_item_pos, search_commit_root,
2041 iterate, ctx, ignore_offset);
2042
2043 return ret;
2044}
2045
2046typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
2047 struct extent_buffer *eb, void *ctx);
2048
2049static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
2050 struct btrfs_path *path,
2051 iterate_irefs_t *iterate, void *ctx)
2052{
2053 int ret = 0;
2054 int slot;
2055 u32 cur;
2056 u32 len;
2057 u32 name_len;
2058 u64 parent = 0;
2059 int found = 0;
2060 struct extent_buffer *eb;
2061 struct btrfs_item *item;
2062 struct btrfs_inode_ref *iref;
2063 struct btrfs_key found_key;
2064
2065 while (!ret) {
2066 ret = btrfs_find_item(fs_root, path, inum,
2067 parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY,
2068 &found_key);
2069
2070 if (ret < 0)
2071 break;
2072 if (ret) {
2073 ret = found ? 0 : -ENOENT;
2074 break;
2075 }
2076 ++found;
2077
2078 parent = found_key.offset;
2079 slot = path->slots[0];
2080 eb = btrfs_clone_extent_buffer(path->nodes[0]);
2081 if (!eb) {
2082 ret = -ENOMEM;
2083 break;
2084 }
2085 btrfs_release_path(path);
2086
2087 item = btrfs_item_nr(slot);
2088 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
2089
2090 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
2091 name_len = btrfs_inode_ref_name_len(eb, iref);
2092
2093 btrfs_debug(fs_root->fs_info,
2094 "following ref at offset %u for inode %llu in tree %llu",
2095 cur, found_key.objectid,
2096 fs_root->root_key.objectid);
2097 ret = iterate(parent, name_len,
2098 (unsigned long)(iref + 1), eb, ctx);
2099 if (ret)
2100 break;
2101 len = sizeof(*iref) + name_len;
2102 iref = (struct btrfs_inode_ref *)((char *)iref + len);
2103 }
2104 free_extent_buffer(eb);
2105 }
2106
2107 btrfs_release_path(path);
2108
2109 return ret;
2110}
2111
2112static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
2113 struct btrfs_path *path,
2114 iterate_irefs_t *iterate, void *ctx)
2115{
2116 int ret;
2117 int slot;
2118 u64 offset = 0;
2119 u64 parent;
2120 int found = 0;
2121 struct extent_buffer *eb;
2122 struct btrfs_inode_extref *extref;
2123 u32 item_size;
2124 u32 cur_offset;
2125 unsigned long ptr;
2126
2127 while (1) {
2128 ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
2129 &offset);
2130 if (ret < 0)
2131 break;
2132 if (ret) {
2133 ret = found ? 0 : -ENOENT;
2134 break;
2135 }
2136 ++found;
2137
2138 slot = path->slots[0];
2139 eb = btrfs_clone_extent_buffer(path->nodes[0]);
2140 if (!eb) {
2141 ret = -ENOMEM;
2142 break;
2143 }
2144 btrfs_release_path(path);
2145
2146 item_size = btrfs_item_size_nr(eb, slot);
2147 ptr = btrfs_item_ptr_offset(eb, slot);
2148 cur_offset = 0;
2149
2150 while (cur_offset < item_size) {
2151 u32 name_len;
2152
2153 extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
2154 parent = btrfs_inode_extref_parent(eb, extref);
2155 name_len = btrfs_inode_extref_name_len(eb, extref);
2156 ret = iterate(parent, name_len,
2157 (unsigned long)&extref->name, eb, ctx);
2158 if (ret)
2159 break;
2160
2161 cur_offset += btrfs_inode_extref_name_len(eb, extref);
2162 cur_offset += sizeof(*extref);
2163 }
2164 free_extent_buffer(eb);
2165
2166 offset++;
2167 }
2168
2169 btrfs_release_path(path);
2170
2171 return ret;
2172}
2173
2174static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
2175 struct btrfs_path *path, iterate_irefs_t *iterate,
2176 void *ctx)
2177{
2178 int ret;
2179 int found_refs = 0;
2180
2181 ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
2182 if (!ret)
2183 ++found_refs;
2184 else if (ret != -ENOENT)
2185 return ret;
2186
2187 ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
2188 if (ret == -ENOENT && found_refs)
2189 return 0;
2190
2191 return ret;
2192}
2193
2194
2195
2196
2197
2198static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
2199 struct extent_buffer *eb, void *ctx)
2200{
2201 struct inode_fs_paths *ipath = ctx;
2202 char *fspath;
2203 char *fspath_min;
2204 int i = ipath->fspath->elem_cnt;
2205 const int s_ptr = sizeof(char *);
2206 u32 bytes_left;
2207
2208 bytes_left = ipath->fspath->bytes_left > s_ptr ?
2209 ipath->fspath->bytes_left - s_ptr : 0;
2210
2211 fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
2212 fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
2213 name_off, eb, inum, fspath_min, bytes_left);
2214 if (IS_ERR(fspath))
2215 return PTR_ERR(fspath);
2216
2217 if (fspath > fspath_min) {
2218 ipath->fspath->val[i] = (u64)(unsigned long)fspath;
2219 ++ipath->fspath->elem_cnt;
2220 ipath->fspath->bytes_left = fspath - fspath_min;
2221 } else {
2222 ++ipath->fspath->elem_missed;
2223 ipath->fspath->bytes_missing += fspath_min - fspath;
2224 ipath->fspath->bytes_left = 0;
2225 }
2226
2227 return 0;
2228}
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
2241{
2242 return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
2243 inode_to_path, ipath);
2244}
2245
2246struct btrfs_data_container *init_data_container(u32 total_bytes)
2247{
2248 struct btrfs_data_container *data;
2249 size_t alloc_bytes;
2250
2251 alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
2252 data = kvmalloc(alloc_bytes, GFP_KERNEL);
2253 if (!data)
2254 return ERR_PTR(-ENOMEM);
2255
2256 if (total_bytes >= sizeof(*data)) {
2257 data->bytes_left = total_bytes - sizeof(*data);
2258 data->bytes_missing = 0;
2259 } else {
2260 data->bytes_missing = sizeof(*data) - total_bytes;
2261 data->bytes_left = 0;
2262 }
2263
2264 data->elem_cnt = 0;
2265 data->elem_missed = 0;
2266
2267 return data;
2268}
2269
2270
2271
2272
2273
2274
2275
2276struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
2277 struct btrfs_path *path)
2278{
2279 struct inode_fs_paths *ifp;
2280 struct btrfs_data_container *fspath;
2281
2282 fspath = init_data_container(total_bytes);
2283 if (IS_ERR(fspath))
2284 return ERR_CAST(fspath);
2285
2286 ifp = kmalloc(sizeof(*ifp), GFP_KERNEL);
2287 if (!ifp) {
2288 kvfree(fspath);
2289 return ERR_PTR(-ENOMEM);
2290 }
2291
2292 ifp->btrfs_path = path;
2293 ifp->fspath = fspath;
2294 ifp->fs_root = fs_root;
2295
2296 return ifp;
2297}
2298
2299void free_ipath(struct inode_fs_paths *ipath)
2300{
2301 if (!ipath)
2302 return;
2303 kvfree(ipath->fspath);
2304 kfree(ipath);
2305}
2306
2307struct btrfs_backref_iter *btrfs_backref_iter_alloc(
2308 struct btrfs_fs_info *fs_info, gfp_t gfp_flag)
2309{
2310 struct btrfs_backref_iter *ret;
2311
2312 ret = kzalloc(sizeof(*ret), gfp_flag);
2313 if (!ret)
2314 return NULL;
2315
2316 ret->path = btrfs_alloc_path();
2317 if (!ret->path) {
2318 kfree(ret);
2319 return NULL;
2320 }
2321
2322
2323 ret->path->search_commit_root = 1;
2324 ret->path->skip_locking = 1;
2325 ret->fs_info = fs_info;
2326
2327 return ret;
2328}
2329
2330int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)
2331{
2332 struct btrfs_fs_info *fs_info = iter->fs_info;
2333 struct btrfs_path *path = iter->path;
2334 struct btrfs_extent_item *ei;
2335 struct btrfs_key key;
2336 int ret;
2337
2338 key.objectid = bytenr;
2339 key.type = BTRFS_METADATA_ITEM_KEY;
2340 key.offset = (u64)-1;
2341 iter->bytenr = bytenr;
2342
2343 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
2344 if (ret < 0)
2345 return ret;
2346 if (ret == 0) {
2347 ret = -EUCLEAN;
2348 goto release;
2349 }
2350 if (path->slots[0] == 0) {
2351 WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
2352 ret = -EUCLEAN;
2353 goto release;
2354 }
2355 path->slots[0]--;
2356
2357 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
2358 if ((key.type != BTRFS_EXTENT_ITEM_KEY &&
2359 key.type != BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {
2360 ret = -ENOENT;
2361 goto release;
2362 }
2363 memcpy(&iter->cur_key, &key, sizeof(key));
2364 iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],
2365 path->slots[0]);
2366 iter->end_ptr = (u32)(iter->item_ptr +
2367 btrfs_item_size_nr(path->nodes[0], path->slots[0]));
2368 ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
2369 struct btrfs_extent_item);
2370
2371
2372
2373
2374
2375
2376
2377
2378 if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {
2379 ret = -ENOTSUPP;
2380 goto release;
2381 }
2382 iter->cur_ptr = (u32)(iter->item_ptr + sizeof(*ei));
2383
2384
2385 if (iter->cur_ptr >= iter->end_ptr) {
2386 ret = btrfs_next_item(fs_info->extent_root, path);
2387
2388
2389 if (ret > 0) {
2390 ret = -ENOENT;
2391 goto release;
2392 }
2393 if (ret < 0)
2394 goto release;
2395
2396 btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key,
2397 path->slots[0]);
2398 if (iter->cur_key.objectid != bytenr ||
2399 (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
2400 iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) {
2401 ret = -ENOENT;
2402 goto release;
2403 }
2404 iter->cur_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],
2405 path->slots[0]);
2406 iter->item_ptr = iter->cur_ptr;
2407 iter->end_ptr = (u32)(iter->item_ptr + btrfs_item_size_nr(
2408 path->nodes[0], path->slots[0]));
2409 }
2410
2411 return 0;
2412release:
2413 btrfs_backref_iter_release(iter);
2414 return ret;
2415}
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427int btrfs_backref_iter_next(struct btrfs_backref_iter *iter)
2428{
2429 struct extent_buffer *eb = btrfs_backref_get_eb(iter);
2430 struct btrfs_path *path = iter->path;
2431 struct btrfs_extent_inline_ref *iref;
2432 int ret;
2433 u32 size;
2434
2435 if (btrfs_backref_iter_is_inline_ref(iter)) {
2436
2437 ASSERT(iter->cur_ptr < iter->end_ptr);
2438
2439 if (btrfs_backref_has_tree_block_info(iter)) {
2440
2441 size = sizeof(struct btrfs_tree_block_info);
2442 } else {
2443
2444 int type;
2445
2446 iref = (struct btrfs_extent_inline_ref *)
2447 ((unsigned long)iter->cur_ptr);
2448 type = btrfs_extent_inline_ref_type(eb, iref);
2449
2450 size = btrfs_extent_inline_ref_size(type);
2451 }
2452 iter->cur_ptr += size;
2453 if (iter->cur_ptr < iter->end_ptr)
2454 return 0;
2455
2456
2457 }
2458
2459
2460 ret = btrfs_next_item(iter->fs_info->extent_root, iter->path);
2461 if (ret)
2462 return ret;
2463
2464 btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key, path->slots[0]);
2465 if (iter->cur_key.objectid != iter->bytenr ||
2466 (iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
2467 iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY))
2468 return 1;
2469 iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],
2470 path->slots[0]);
2471 iter->cur_ptr = iter->item_ptr;
2472 iter->end_ptr = iter->item_ptr + (u32)btrfs_item_size_nr(path->nodes[0],
2473 path->slots[0]);
2474 return 0;
2475}
2476
2477void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,
2478 struct btrfs_backref_cache *cache, int is_reloc)
2479{
2480 int i;
2481
2482 cache->rb_root = RB_ROOT;
2483 for (i = 0; i < BTRFS_MAX_LEVEL; i++)
2484 INIT_LIST_HEAD(&cache->pending[i]);
2485 INIT_LIST_HEAD(&cache->changed);
2486 INIT_LIST_HEAD(&cache->detached);
2487 INIT_LIST_HEAD(&cache->leaves);
2488 INIT_LIST_HEAD(&cache->pending_edge);
2489 INIT_LIST_HEAD(&cache->useless_node);
2490 cache->fs_info = fs_info;
2491 cache->is_reloc = is_reloc;
2492}
2493
2494struct btrfs_backref_node *btrfs_backref_alloc_node(
2495 struct btrfs_backref_cache *cache, u64 bytenr, int level)
2496{
2497 struct btrfs_backref_node *node;
2498
2499 ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL);
2500 node = kzalloc(sizeof(*node), GFP_NOFS);
2501 if (!node)
2502 return node;
2503
2504 INIT_LIST_HEAD(&node->list);
2505 INIT_LIST_HEAD(&node->upper);
2506 INIT_LIST_HEAD(&node->lower);
2507 RB_CLEAR_NODE(&node->rb_node);
2508 cache->nr_nodes++;
2509 node->level = level;
2510 node->bytenr = bytenr;
2511
2512 return node;
2513}
2514
2515struct btrfs_backref_edge *btrfs_backref_alloc_edge(
2516 struct btrfs_backref_cache *cache)
2517{
2518 struct btrfs_backref_edge *edge;
2519
2520 edge = kzalloc(sizeof(*edge), GFP_NOFS);
2521 if (edge)
2522 cache->nr_edges++;
2523 return edge;
2524}
2525
2526
2527
2528
2529
2530
2531
2532
2533void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,
2534 struct btrfs_backref_node *node)
2535{
2536 struct btrfs_backref_node *upper;
2537 struct btrfs_backref_edge *edge;
2538
2539 if (!node)
2540 return;
2541
2542 BUG_ON(!node->lowest && !node->detached);
2543 while (!list_empty(&node->upper)) {
2544 edge = list_entry(node->upper.next, struct btrfs_backref_edge,
2545 list[LOWER]);
2546 upper = edge->node[UPPER];
2547 list_del(&edge->list[LOWER]);
2548 list_del(&edge->list[UPPER]);
2549 btrfs_backref_free_edge(cache, edge);
2550
2551
2552
2553
2554
2555 if (list_empty(&upper->lower)) {
2556 list_add_tail(&upper->lower, &cache->leaves);
2557 upper->lowest = 1;
2558 }
2559 }
2560
2561 btrfs_backref_drop_node(cache, node);
2562}
2563
2564
2565
2566
2567void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)
2568{
2569 struct btrfs_backref_node *node;
2570 int i;
2571
2572 while (!list_empty(&cache->detached)) {
2573 node = list_entry(cache->detached.next,
2574 struct btrfs_backref_node, list);
2575 btrfs_backref_cleanup_node(cache, node);
2576 }
2577
2578 while (!list_empty(&cache->leaves)) {
2579 node = list_entry(cache->leaves.next,
2580 struct btrfs_backref_node, lower);
2581 btrfs_backref_cleanup_node(cache, node);
2582 }
2583
2584 cache->last_trans = 0;
2585
2586 for (i = 0; i < BTRFS_MAX_LEVEL; i++)
2587 ASSERT(list_empty(&cache->pending[i]));
2588 ASSERT(list_empty(&cache->pending_edge));
2589 ASSERT(list_empty(&cache->useless_node));
2590 ASSERT(list_empty(&cache->changed));
2591 ASSERT(list_empty(&cache->detached));
2592 ASSERT(RB_EMPTY_ROOT(&cache->rb_root));
2593 ASSERT(!cache->nr_nodes);
2594 ASSERT(!cache->nr_edges);
2595}
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609static int handle_direct_tree_backref(struct btrfs_backref_cache *cache,
2610 struct btrfs_key *ref_key,
2611 struct btrfs_backref_node *cur)
2612{
2613 struct btrfs_backref_edge *edge;
2614 struct btrfs_backref_node *upper;
2615 struct rb_node *rb_node;
2616
2617 ASSERT(ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY);
2618
2619
2620 if (ref_key->objectid == ref_key->offset) {
2621 struct btrfs_root *root;
2622
2623 cur->is_reloc_root = 1;
2624
2625 if (cache->is_reloc) {
2626 root = find_reloc_root(cache->fs_info, cur->bytenr);
2627 if (!root)
2628 return -ENOENT;
2629 cur->root = root;
2630 } else {
2631
2632
2633
2634
2635 list_add(&cur->list, &cache->useless_node);
2636 }
2637 return 0;
2638 }
2639
2640 edge = btrfs_backref_alloc_edge(cache);
2641 if (!edge)
2642 return -ENOMEM;
2643
2644 rb_node = rb_simple_search(&cache->rb_root, ref_key->offset);
2645 if (!rb_node) {
2646
2647 upper = btrfs_backref_alloc_node(cache, ref_key->offset,
2648 cur->level + 1);
2649 if (!upper) {
2650 btrfs_backref_free_edge(cache, edge);
2651 return -ENOMEM;
2652 }
2653
2654
2655
2656
2657
2658 list_add_tail(&edge->list[UPPER], &cache->pending_edge);
2659 } else {
2660
2661 upper = rb_entry(rb_node, struct btrfs_backref_node, rb_node);
2662 ASSERT(upper->checked);
2663 INIT_LIST_HEAD(&edge->list[UPPER]);
2664 }
2665 btrfs_backref_link_edge(edge, cur, upper, LINK_LOWER);
2666 return 0;
2667}
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681static int handle_indirect_tree_backref(struct btrfs_backref_cache *cache,
2682 struct btrfs_path *path,
2683 struct btrfs_key *ref_key,
2684 struct btrfs_key *tree_key,
2685 struct btrfs_backref_node *cur)
2686{
2687 struct btrfs_fs_info *fs_info = cache->fs_info;
2688 struct btrfs_backref_node *upper;
2689 struct btrfs_backref_node *lower;
2690 struct btrfs_backref_edge *edge;
2691 struct extent_buffer *eb;
2692 struct btrfs_root *root;
2693 struct rb_node *rb_node;
2694 int level;
2695 bool need_check = true;
2696 int ret;
2697
2698 root = btrfs_get_fs_root(fs_info, ref_key->offset, false);
2699 if (IS_ERR(root))
2700 return PTR_ERR(root);
2701 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
2702 cur->cowonly = 1;
2703
2704 if (btrfs_root_level(&root->root_item) == cur->level) {
2705
2706 ASSERT(btrfs_root_bytenr(&root->root_item) == cur->bytenr);
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717 if (btrfs_should_ignore_reloc_root(root) && cache->is_reloc) {
2718 btrfs_put_root(root);
2719 list_add(&cur->list, &cache->useless_node);
2720 } else {
2721 cur->root = root;
2722 }
2723 return 0;
2724 }
2725
2726 level = cur->level + 1;
2727
2728
2729 path->search_commit_root = 1;
2730 path->skip_locking = 1;
2731 path->lowest_level = level;
2732 ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0);
2733 path->lowest_level = 0;
2734 if (ret < 0) {
2735 btrfs_put_root(root);
2736 return ret;
2737 }
2738 if (ret > 0 && path->slots[level] > 0)
2739 path->slots[level]--;
2740
2741 eb = path->nodes[level];
2742 if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) {
2743 btrfs_err(fs_info,
2744"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
2745 cur->bytenr, level - 1, root->root_key.objectid,
2746 tree_key->objectid, tree_key->type, tree_key->offset);
2747 btrfs_put_root(root);
2748 ret = -ENOENT;
2749 goto out;
2750 }
2751 lower = cur;
2752
2753
2754 for (; level < BTRFS_MAX_LEVEL; level++) {
2755 if (!path->nodes[level]) {
2756 ASSERT(btrfs_root_bytenr(&root->root_item) ==
2757 lower->bytenr);
2758
2759 if (btrfs_should_ignore_reloc_root(root) &&
2760 cache->is_reloc) {
2761 btrfs_put_root(root);
2762 list_add(&lower->list, &cache->useless_node);
2763 } else {
2764 lower->root = root;
2765 }
2766 break;
2767 }
2768
2769 edge = btrfs_backref_alloc_edge(cache);
2770 if (!edge) {
2771 btrfs_put_root(root);
2772 ret = -ENOMEM;
2773 goto out;
2774 }
2775
2776 eb = path->nodes[level];
2777 rb_node = rb_simple_search(&cache->rb_root, eb->start);
2778 if (!rb_node) {
2779 upper = btrfs_backref_alloc_node(cache, eb->start,
2780 lower->level + 1);
2781 if (!upper) {
2782 btrfs_put_root(root);
2783 btrfs_backref_free_edge(cache, edge);
2784 ret = -ENOMEM;
2785 goto out;
2786 }
2787 upper->owner = btrfs_header_owner(eb);
2788 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
2789 upper->cowonly = 1;
2790
2791
2792
2793
2794
2795 if (btrfs_block_can_be_shared(root, eb))
2796 upper->checked = 0;
2797 else
2798 upper->checked = 1;
2799
2800
2801
2802
2803
2804
2805 if (!upper->checked && need_check) {
2806 need_check = false;
2807 list_add_tail(&edge->list[UPPER],
2808 &cache->pending_edge);
2809 } else {
2810 if (upper->checked)
2811 need_check = true;
2812 INIT_LIST_HEAD(&edge->list[UPPER]);
2813 }
2814 } else {
2815 upper = rb_entry(rb_node, struct btrfs_backref_node,
2816 rb_node);
2817 ASSERT(upper->checked);
2818 INIT_LIST_HEAD(&edge->list[UPPER]);
2819 if (!upper->owner)
2820 upper->owner = btrfs_header_owner(eb);
2821 }
2822 btrfs_backref_link_edge(edge, lower, upper, LINK_LOWER);
2823
2824 if (rb_node) {
2825 btrfs_put_root(root);
2826 break;
2827 }
2828 lower = upper;
2829 upper = NULL;
2830 }
2831out:
2832 btrfs_release_path(path);
2833 return ret;
2834}
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847int btrfs_backref_add_tree_node(struct btrfs_backref_cache *cache,
2848 struct btrfs_path *path,
2849 struct btrfs_backref_iter *iter,
2850 struct btrfs_key *node_key,
2851 struct btrfs_backref_node *cur)
2852{
2853 struct btrfs_fs_info *fs_info = cache->fs_info;
2854 struct btrfs_backref_edge *edge;
2855 struct btrfs_backref_node *exist;
2856 int ret;
2857
2858 ret = btrfs_backref_iter_start(iter, cur->bytenr);
2859 if (ret < 0)
2860 return ret;
2861
2862
2863
2864
2865 if (btrfs_backref_has_tree_block_info(iter)) {
2866 ret = btrfs_backref_iter_next(iter);
2867 if (ret < 0)
2868 goto out;
2869
2870 if (ret > 0) {
2871 ret = -EUCLEAN;
2872 goto out;
2873 }
2874 }
2875 WARN_ON(cur->checked);
2876 if (!list_empty(&cur->upper)) {
2877
2878
2879
2880
2881 ASSERT(list_is_singular(&cur->upper));
2882 edge = list_entry(cur->upper.next, struct btrfs_backref_edge,
2883 list[LOWER]);
2884 ASSERT(list_empty(&edge->list[UPPER]));
2885 exist = edge->node[UPPER];
2886
2887
2888
2889
2890 if (!exist->checked)
2891 list_add_tail(&edge->list[UPPER], &cache->pending_edge);
2892 } else {
2893 exist = NULL;
2894 }
2895
2896 for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
2897 struct extent_buffer *eb;
2898 struct btrfs_key key;
2899 int type;
2900
2901 cond_resched();
2902 eb = btrfs_backref_get_eb(iter);
2903
2904 key.objectid = iter->bytenr;
2905 if (btrfs_backref_iter_is_inline_ref(iter)) {
2906 struct btrfs_extent_inline_ref *iref;
2907
2908
2909 iref = (struct btrfs_extent_inline_ref *)
2910 ((unsigned long)iter->cur_ptr);
2911 type = btrfs_get_extent_inline_ref_type(eb, iref,
2912 BTRFS_REF_TYPE_BLOCK);
2913 if (type == BTRFS_REF_TYPE_INVALID) {
2914 ret = -EUCLEAN;
2915 goto out;
2916 }
2917 key.type = type;
2918 key.offset = btrfs_extent_inline_ref_offset(eb, iref);
2919 } else {
2920 key.type = iter->cur_key.type;
2921 key.offset = iter->cur_key.offset;
2922 }
2923
2924
2925
2926
2927
2928 if (exist &&
2929 ((key.type == BTRFS_TREE_BLOCK_REF_KEY &&
2930 exist->owner == key.offset) ||
2931 (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&
2932 exist->bytenr == key.offset))) {
2933 exist = NULL;
2934 continue;
2935 }
2936
2937
2938 if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2939 ret = handle_direct_tree_backref(cache, &key, cur);
2940 if (ret < 0)
2941 goto out;
2942 continue;
2943 } else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
2944 ret = -EINVAL;
2945 btrfs_print_v0_err(fs_info);
2946 btrfs_handle_fs_error(fs_info, ret, NULL);
2947 goto out;
2948 } else if (key.type != BTRFS_TREE_BLOCK_REF_KEY) {
2949 continue;
2950 }
2951
2952
2953
2954
2955
2956
2957 ret = handle_indirect_tree_backref(cache, path, &key, node_key,
2958 cur);
2959 if (ret < 0)
2960 goto out;
2961 }
2962 ret = 0;
2963 cur->checked = 1;
2964 WARN_ON(exist);
2965out:
2966 btrfs_backref_iter_release(iter);
2967 return ret;
2968}
2969
2970
2971
2972
2973int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
2974 struct btrfs_backref_node *start)
2975{
2976 struct list_head *useless_node = &cache->useless_node;
2977 struct btrfs_backref_edge *edge;
2978 struct rb_node *rb_node;
2979 LIST_HEAD(pending_edge);
2980
2981 ASSERT(start->checked);
2982
2983
2984 if (!start->cowonly) {
2985 rb_node = rb_simple_insert(&cache->rb_root, start->bytenr,
2986 &start->rb_node);
2987 if (rb_node)
2988 btrfs_backref_panic(cache->fs_info, start->bytenr,
2989 -EEXIST);
2990 list_add_tail(&start->lower, &cache->leaves);
2991 }
2992
2993
2994
2995
2996
2997
2998 list_for_each_entry(edge, &start->upper, list[LOWER])
2999 list_add_tail(&edge->list[UPPER], &pending_edge);
3000
3001 while (!list_empty(&pending_edge)) {
3002 struct btrfs_backref_node *upper;
3003 struct btrfs_backref_node *lower;
3004
3005 edge = list_first_entry(&pending_edge,
3006 struct btrfs_backref_edge, list[UPPER]);
3007 list_del_init(&edge->list[UPPER]);
3008 upper = edge->node[UPPER];
3009 lower = edge->node[LOWER];
3010
3011
3012 if (upper->detached) {
3013 list_del(&edge->list[LOWER]);
3014 btrfs_backref_free_edge(cache, edge);
3015
3016
3017 if (list_empty(&lower->upper))
3018 list_add(&lower->list, useless_node);
3019 continue;
3020 }
3021
3022
3023
3024
3025
3026
3027
3028
3029 if (!RB_EMPTY_NODE(&upper->rb_node)) {
3030 if (upper->lowest) {
3031 list_del_init(&upper->lower);
3032 upper->lowest = 0;
3033 }
3034
3035 list_add_tail(&edge->list[UPPER], &upper->lower);
3036 continue;
3037 }
3038
3039
3040 if (!upper->checked) {
3041 ASSERT(0);
3042 return -EUCLEAN;
3043 }
3044
3045
3046 if (start->cowonly != upper->cowonly) {
3047 ASSERT(0);
3048 return -EUCLEAN;
3049 }
3050
3051
3052 if (!upper->cowonly) {
3053 rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr,
3054 &upper->rb_node);
3055 if (rb_node) {
3056 btrfs_backref_panic(cache->fs_info,
3057 upper->bytenr, -EEXIST);
3058 return -EUCLEAN;
3059 }
3060 }
3061
3062 list_add_tail(&edge->list[UPPER], &upper->lower);
3063
3064
3065
3066
3067
3068 list_for_each_entry(edge, &upper->upper, list[LOWER])
3069 list_add_tail(&edge->list[UPPER], &pending_edge);
3070 }
3071 return 0;
3072}
3073
3074void btrfs_backref_error_cleanup(struct btrfs_backref_cache *cache,
3075 struct btrfs_backref_node *node)
3076{
3077 struct btrfs_backref_node *lower;
3078 struct btrfs_backref_node *upper;
3079 struct btrfs_backref_edge *edge;
3080
3081 while (!list_empty(&cache->useless_node)) {
3082 lower = list_first_entry(&cache->useless_node,
3083 struct btrfs_backref_node, list);
3084 list_del_init(&lower->list);
3085 }
3086 while (!list_empty(&cache->pending_edge)) {
3087 edge = list_first_entry(&cache->pending_edge,
3088 struct btrfs_backref_edge, list[UPPER]);
3089 list_del(&edge->list[UPPER]);
3090 list_del(&edge->list[LOWER]);
3091 lower = edge->node[LOWER];
3092 upper = edge->node[UPPER];
3093 btrfs_backref_free_edge(cache, edge);
3094
3095
3096
3097
3098
3099 if (list_empty(&lower->upper) &&
3100 RB_EMPTY_NODE(&lower->rb_node))
3101 list_add(&lower->list, &cache->useless_node);
3102
3103 if (!RB_EMPTY_NODE(&upper->rb_node))
3104 continue;
3105
3106
3107 list_for_each_entry(edge, &upper->upper, list[LOWER])
3108 list_add_tail(&edge->list[UPPER],
3109 &cache->pending_edge);
3110 if (list_empty(&upper->upper))
3111 list_add(&upper->list, &cache->useless_node);
3112 }
3113
3114 while (!list_empty(&cache->useless_node)) {
3115 lower = list_first_entry(&cache->useless_node,
3116 struct btrfs_backref_node, list);
3117 list_del_init(&lower->list);
3118 if (lower == node)
3119 node = NULL;
3120 btrfs_backref_drop_node(cache, lower);
3121 }
3122
3123 btrfs_backref_cleanup_node(cache, node);
3124 ASSERT(list_empty(&cache->useless_node) &&
3125 list_empty(&cache->pending_edge));
3126}
3127