2 * Copyright (C) 2011 STRATO. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
23 #include "transaction.h"
24 #include "delayed-ref.h"
28 * this structure records all encountered refs on the way up to the root
31 struct list_head list
;
33 struct btrfs_key key_for_search
;
41 * the rules for all callers of this function are:
42 * - obtaining the parent is the goal
43 * - if you add a key, you must know that it is a correct key
44 * - if you cannot add the parent or a correct key, then we will look into the
45 * block later to set a correct key
49 * backref type | shared | indirect | shared | indirect
50 * information | tree | tree | data | data
51 * --------------------+--------+----------+--------+----------
52 * parent logical | y | - | - | -
53 * key to resolve | - | y | y | y
54 * tree block logical | - | - | - | -
55 * root for resolving | y | y | y | y
57 * - column 1: we've the parent -> done
58 * - column 2, 3, 4: we use the key to find the parent
60 * on disk refs (inline or keyed)
61 * ==============================
62 * backref type | shared | indirect | shared | indirect
63 * information | tree | tree | data | data
64 * --------------------+--------+----------+--------+----------
65 * parent logical | y | - | y | -
66 * key to resolve | - | - | - | y
67 * tree block logical | y | y | y | y
68 * root for resolving | - | y | y | y
70 * - column 1, 3: we've the parent -> done
71 * - column 2: we take the first key from the block to find the parent
72 * (see __add_missing_keys)
73 * - column 4: we use the key to find the parent
75 * additional information that's available but not required to find the parent
76 * block might help in merging entries to gain some speed.
79 static int __add_prelim_ref(struct list_head
*head
, u64 root_id
,
80 struct btrfs_key
*key
, int level
,
81 u64 parent
, u64 wanted_disk_byte
, int count
)
83 struct __prelim_ref
*ref
;
85 /* in case we're adding delayed refs, we're holding the refs spinlock */
86 ref
= kmalloc(sizeof(*ref
), GFP_ATOMIC
);
90 ref
->root_id
= root_id
;
92 ref
->key_for_search
= *key
;
94 memset(&ref
->key_for_search
, 0, sizeof(ref
->key_for_search
));
99 ref
->wanted_disk_byte
= wanted_disk_byte
;
100 list_add_tail(&ref
->list
, head
);
105 static int add_all_parents(struct btrfs_root
*root
, struct btrfs_path
*path
,
106 struct ulist
*parents
,
107 struct extent_buffer
*eb
, int level
,
108 u64 wanted_objectid
, u64 wanted_disk_byte
)
112 struct btrfs_file_extent_item
*fi
;
113 struct btrfs_key key
;
117 ret
= ulist_add(parents
, eb
->start
, 0, GFP_NOFS
);
125 * if the current leaf is full with EXTENT_DATA items, we must
126 * check the next one if that holds a reference as well.
127 * ref->count cannot be used to skip this check.
128 * repeat this until we don't find any additional EXTENT_DATA items.
131 ret
= btrfs_next_leaf(root
, path
);
138 for (slot
= 0; slot
< btrfs_header_nritems(eb
); ++slot
) {
139 btrfs_item_key_to_cpu(eb
, &key
, slot
);
140 if (key
.objectid
!= wanted_objectid
||
141 key
.type
!= BTRFS_EXTENT_DATA_KEY
)
143 fi
= btrfs_item_ptr(eb
, slot
,
144 struct btrfs_file_extent_item
);
145 disk_byte
= btrfs_file_extent_disk_bytenr(eb
, fi
);
146 if (disk_byte
== wanted_disk_byte
)
155 * resolve an indirect backref in the form (root_id, key, level)
156 * to a logical address
158 static int __resolve_indirect_ref(struct btrfs_fs_info
*fs_info
,
159 int search_commit_root
,
160 struct __prelim_ref
*ref
,
161 struct ulist
*parents
)
163 struct btrfs_path
*path
;
164 struct btrfs_root
*root
;
165 struct btrfs_key root_key
;
166 struct btrfs_key key
= {0};
167 struct extent_buffer
*eb
;
170 int level
= ref
->level
;
172 path
= btrfs_alloc_path();
175 path
->search_commit_root
= !!search_commit_root
;
177 root_key
.objectid
= ref
->root_id
;
178 root_key
.type
= BTRFS_ROOT_ITEM_KEY
;
179 root_key
.offset
= (u64
)-1;
180 root
= btrfs_read_fs_root_no_name(fs_info
, &root_key
);
187 root_level
= btrfs_header_level(root
->node
);
190 if (root_level
+ 1 == level
)
193 path
->lowest_level
= level
;
194 ret
= btrfs_search_slot(NULL
, root
, &ref
->key_for_search
, path
, 0, 0);
195 pr_debug("search slot in root %llu (level %d, ref count %d) returned "
196 "%d for key (%llu %u %llu)\n",
197 (unsigned long long)ref
->root_id
, level
, ref
->count
, ret
,
198 (unsigned long long)ref
->key_for_search
.objectid
,
199 ref
->key_for_search
.type
,
200 (unsigned long long)ref
->key_for_search
.offset
);
204 eb
= path
->nodes
[level
];
212 if (ret
== 1 && path
->slots
[0] >= btrfs_header_nritems(eb
)) {
213 ret
= btrfs_next_leaf(root
, path
);
219 btrfs_item_key_to_cpu(eb
, &key
, path
->slots
[0]);
222 /* the last two parameters will only be used for level == 0 */
223 ret
= add_all_parents(root
, path
, parents
, eb
, level
, key
.objectid
,
224 ref
->wanted_disk_byte
);
226 btrfs_free_path(path
);
231 * resolve all indirect backrefs from the list
233 static int __resolve_indirect_refs(struct btrfs_fs_info
*fs_info
,
234 int search_commit_root
,
235 struct list_head
*head
)
239 struct __prelim_ref
*ref
;
240 struct __prelim_ref
*ref_safe
;
241 struct __prelim_ref
*new_ref
;
242 struct ulist
*parents
;
243 struct ulist_node
*node
;
244 struct ulist_iterator uiter
;
246 parents
= ulist_alloc(GFP_NOFS
);
251 * _safe allows us to insert directly after the current item without
252 * iterating over the newly inserted items.
253 * we're also allowed to re-assign ref during iteration.
255 list_for_each_entry_safe(ref
, ref_safe
, head
, list
) {
256 if (ref
->parent
) /* already direct */
260 err
= __resolve_indirect_ref(fs_info
, search_commit_root
,
268 /* we put the first parent into the ref at hand */
269 ULIST_ITER_INIT(&uiter
);
270 node
= ulist_next(parents
, &uiter
);
271 ref
->parent
= node
? node
->val
: 0;
273 /* additional parents require new refs being added here */
274 while ((node
= ulist_next(parents
, &uiter
))) {
275 new_ref
= kmalloc(sizeof(*new_ref
), GFP_NOFS
);
280 memcpy(new_ref
, ref
, sizeof(*ref
));
281 new_ref
->parent
= node
->val
;
282 list_add(&new_ref
->list
, &ref
->list
);
284 ulist_reinit(parents
);
291 static inline int ref_for_same_block(struct __prelim_ref
*ref1
,
292 struct __prelim_ref
*ref2
)
294 if (ref1
->level
!= ref2
->level
)
296 if (ref1
->root_id
!= ref2
->root_id
)
298 if (ref1
->key_for_search
.type
!= ref2
->key_for_search
.type
)
300 if (ref1
->key_for_search
.objectid
!= ref2
->key_for_search
.objectid
)
302 if (ref1
->key_for_search
.offset
!= ref2
->key_for_search
.offset
)
304 if (ref1
->parent
!= ref2
->parent
)
311 * read tree blocks and add keys where required.
313 static int __add_missing_keys(struct btrfs_fs_info
*fs_info
,
314 struct list_head
*head
)
316 struct list_head
*pos
;
317 struct extent_buffer
*eb
;
319 list_for_each(pos
, head
) {
320 struct __prelim_ref
*ref
;
321 ref
= list_entry(pos
, struct __prelim_ref
, list
);
325 if (ref
->key_for_search
.type
)
327 BUG_ON(!ref
->wanted_disk_byte
);
328 eb
= read_tree_block(fs_info
->tree_root
, ref
->wanted_disk_byte
,
329 fs_info
->tree_root
->leafsize
, 0);
331 btrfs_tree_read_lock(eb
);
332 if (btrfs_header_level(eb
) == 0)
333 btrfs_item_key_to_cpu(eb
, &ref
->key_for_search
, 0);
335 btrfs_node_key_to_cpu(eb
, &ref
->key_for_search
, 0);
336 btrfs_tree_read_unlock(eb
);
337 free_extent_buffer(eb
);
343 * merge two lists of backrefs and adjust counts accordingly
345 * mode = 1: merge identical keys, if key is set
346 * FIXME: if we add more keys in __add_prelim_ref, we can merge more here.
347 * additionally, we could even add a key range for the blocks we
348 * looked into to merge even more (-> replace unresolved refs by those
350 * mode = 2: merge identical parents
352 static int __merge_refs(struct list_head
*head
, int mode
)
354 struct list_head
*pos1
;
356 list_for_each(pos1
, head
) {
357 struct list_head
*n2
;
358 struct list_head
*pos2
;
359 struct __prelim_ref
*ref1
;
361 ref1
= list_entry(pos1
, struct __prelim_ref
, list
);
363 for (pos2
= pos1
->next
, n2
= pos2
->next
; pos2
!= head
;
364 pos2
= n2
, n2
= pos2
->next
) {
365 struct __prelim_ref
*ref2
;
366 struct __prelim_ref
*xchg
;
368 ref2
= list_entry(pos2
, struct __prelim_ref
, list
);
371 if (!ref_for_same_block(ref1
, ref2
))
373 if (!ref1
->parent
&& ref2
->parent
) {
378 ref1
->count
+= ref2
->count
;
380 if (ref1
->parent
!= ref2
->parent
)
382 ref1
->count
+= ref2
->count
;
384 list_del(&ref2
->list
);
393 * add all currently queued delayed refs from this head whose seq nr is
394 * smaller or equal that seq to the list
396 static int __add_delayed_refs(struct btrfs_delayed_ref_head
*head
, u64 seq
,
397 struct list_head
*prefs
)
399 struct btrfs_delayed_extent_op
*extent_op
= head
->extent_op
;
400 struct rb_node
*n
= &head
->node
.rb_node
;
401 struct btrfs_key key
;
402 struct btrfs_key op_key
= {0};
406 if (extent_op
&& extent_op
->update_key
)
407 btrfs_disk_key_to_cpu(&op_key
, &extent_op
->key
);
409 while ((n
= rb_prev(n
))) {
410 struct btrfs_delayed_ref_node
*node
;
411 node
= rb_entry(n
, struct btrfs_delayed_ref_node
,
413 if (node
->bytenr
!= head
->node
.bytenr
)
415 WARN_ON(node
->is_head
);
420 switch (node
->action
) {
421 case BTRFS_ADD_DELAYED_EXTENT
:
422 case BTRFS_UPDATE_DELAYED_HEAD
:
425 case BTRFS_ADD_DELAYED_REF
:
428 case BTRFS_DROP_DELAYED_REF
:
434 switch (node
->type
) {
435 case BTRFS_TREE_BLOCK_REF_KEY
: {
436 struct btrfs_delayed_tree_ref
*ref
;
438 ref
= btrfs_delayed_node_to_tree_ref(node
);
439 ret
= __add_prelim_ref(prefs
, ref
->root
, &op_key
,
440 ref
->level
+ 1, 0, node
->bytenr
,
441 node
->ref_mod
* sgn
);
444 case BTRFS_SHARED_BLOCK_REF_KEY
: {
445 struct btrfs_delayed_tree_ref
*ref
;
447 ref
= btrfs_delayed_node_to_tree_ref(node
);
448 ret
= __add_prelim_ref(prefs
, ref
->root
, NULL
,
449 ref
->level
+ 1, ref
->parent
,
451 node
->ref_mod
* sgn
);
454 case BTRFS_EXTENT_DATA_REF_KEY
: {
455 struct btrfs_delayed_data_ref
*ref
;
456 ref
= btrfs_delayed_node_to_data_ref(node
);
458 key
.objectid
= ref
->objectid
;
459 key
.type
= BTRFS_EXTENT_DATA_KEY
;
460 key
.offset
= ref
->offset
;
461 ret
= __add_prelim_ref(prefs
, ref
->root
, &key
, 0, 0,
463 node
->ref_mod
* sgn
);
466 case BTRFS_SHARED_DATA_REF_KEY
: {
467 struct btrfs_delayed_data_ref
*ref
;
469 ref
= btrfs_delayed_node_to_data_ref(node
);
471 key
.objectid
= ref
->objectid
;
472 key
.type
= BTRFS_EXTENT_DATA_KEY
;
473 key
.offset
= ref
->offset
;
474 ret
= __add_prelim_ref(prefs
, ref
->root
, &key
, 0,
475 ref
->parent
, node
->bytenr
,
476 node
->ref_mod
* sgn
);
489 * add all inline backrefs for bytenr to the list
491 static int __add_inline_refs(struct btrfs_fs_info
*fs_info
,
492 struct btrfs_path
*path
, u64 bytenr
,
493 int *info_level
, struct list_head
*prefs
)
497 struct extent_buffer
*leaf
;
498 struct btrfs_key key
;
501 struct btrfs_extent_item
*ei
;
506 * enumerate all inline refs
508 leaf
= path
->nodes
[0];
509 slot
= path
->slots
[0];
511 item_size
= btrfs_item_size_nr(leaf
, slot
);
512 BUG_ON(item_size
< sizeof(*ei
));
514 ei
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_item
);
515 flags
= btrfs_extent_flags(leaf
, ei
);
517 ptr
= (unsigned long)(ei
+ 1);
518 end
= (unsigned long)ei
+ item_size
;
520 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
) {
521 struct btrfs_tree_block_info
*info
;
523 info
= (struct btrfs_tree_block_info
*)ptr
;
524 *info_level
= btrfs_tree_block_level(leaf
, info
);
525 ptr
+= sizeof(struct btrfs_tree_block_info
);
528 BUG_ON(!(flags
& BTRFS_EXTENT_FLAG_DATA
));
532 struct btrfs_extent_inline_ref
*iref
;
536 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
537 type
= btrfs_extent_inline_ref_type(leaf
, iref
);
538 offset
= btrfs_extent_inline_ref_offset(leaf
, iref
);
541 case BTRFS_SHARED_BLOCK_REF_KEY
:
542 ret
= __add_prelim_ref(prefs
, 0, NULL
,
543 *info_level
+ 1, offset
,
546 case BTRFS_SHARED_DATA_REF_KEY
: {
547 struct btrfs_shared_data_ref
*sdref
;
550 sdref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
551 count
= btrfs_shared_data_ref_count(leaf
, sdref
);
552 ret
= __add_prelim_ref(prefs
, 0, NULL
, 0, offset
,
556 case BTRFS_TREE_BLOCK_REF_KEY
:
557 ret
= __add_prelim_ref(prefs
, offset
, NULL
,
561 case BTRFS_EXTENT_DATA_REF_KEY
: {
562 struct btrfs_extent_data_ref
*dref
;
566 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
567 count
= btrfs_extent_data_ref_count(leaf
, dref
);
568 key
.objectid
= btrfs_extent_data_ref_objectid(leaf
,
570 key
.type
= BTRFS_EXTENT_DATA_KEY
;
571 key
.offset
= btrfs_extent_data_ref_offset(leaf
, dref
);
572 root
= btrfs_extent_data_ref_root(leaf
, dref
);
573 ret
= __add_prelim_ref(prefs
, root
, &key
, 0, 0,
581 ptr
+= btrfs_extent_inline_ref_size(type
);
588 * add all non-inline backrefs for bytenr to the list
590 static int __add_keyed_refs(struct btrfs_fs_info
*fs_info
,
591 struct btrfs_path
*path
, u64 bytenr
,
592 int info_level
, struct list_head
*prefs
)
594 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
597 struct extent_buffer
*leaf
;
598 struct btrfs_key key
;
601 ret
= btrfs_next_item(extent_root
, path
);
609 slot
= path
->slots
[0];
610 leaf
= path
->nodes
[0];
611 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
613 if (key
.objectid
!= bytenr
)
615 if (key
.type
< BTRFS_TREE_BLOCK_REF_KEY
)
617 if (key
.type
> BTRFS_SHARED_DATA_REF_KEY
)
621 case BTRFS_SHARED_BLOCK_REF_KEY
:
622 ret
= __add_prelim_ref(prefs
, 0, NULL
,
623 info_level
+ 1, key
.offset
,
626 case BTRFS_SHARED_DATA_REF_KEY
: {
627 struct btrfs_shared_data_ref
*sdref
;
630 sdref
= btrfs_item_ptr(leaf
, slot
,
631 struct btrfs_shared_data_ref
);
632 count
= btrfs_shared_data_ref_count(leaf
, sdref
);
633 ret
= __add_prelim_ref(prefs
, 0, NULL
, 0, key
.offset
,
637 case BTRFS_TREE_BLOCK_REF_KEY
:
638 ret
= __add_prelim_ref(prefs
, key
.offset
, NULL
,
642 case BTRFS_EXTENT_DATA_REF_KEY
: {
643 struct btrfs_extent_data_ref
*dref
;
647 dref
= btrfs_item_ptr(leaf
, slot
,
648 struct btrfs_extent_data_ref
);
649 count
= btrfs_extent_data_ref_count(leaf
, dref
);
650 key
.objectid
= btrfs_extent_data_ref_objectid(leaf
,
652 key
.type
= BTRFS_EXTENT_DATA_KEY
;
653 key
.offset
= btrfs_extent_data_ref_offset(leaf
, dref
);
654 root
= btrfs_extent_data_ref_root(leaf
, dref
);
655 ret
= __add_prelim_ref(prefs
, root
, &key
, 0, 0,
669 * this adds all existing backrefs (inline backrefs, backrefs and delayed
670 * refs) for the given bytenr to the refs list, merges duplicates and resolves
671 * indirect refs to their parent bytenr.
672 * When roots are found, they're added to the roots list
674 * FIXME some caching might speed things up
676 static int find_parent_nodes(struct btrfs_trans_handle
*trans
,
677 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
678 u64 seq
, struct ulist
*refs
, struct ulist
*roots
)
680 struct btrfs_key key
;
681 struct btrfs_path
*path
;
682 struct btrfs_delayed_ref_root
*delayed_refs
= NULL
;
683 struct btrfs_delayed_ref_head
*head
;
686 int search_commit_root
= (trans
== BTRFS_BACKREF_SEARCH_COMMIT_ROOT
);
687 struct list_head prefs_delayed
;
688 struct list_head prefs
;
689 struct __prelim_ref
*ref
;
691 INIT_LIST_HEAD(&prefs
);
692 INIT_LIST_HEAD(&prefs_delayed
);
694 key
.objectid
= bytenr
;
695 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
696 key
.offset
= (u64
)-1;
698 path
= btrfs_alloc_path();
701 path
->search_commit_root
= !!search_commit_root
;
704 * grab both a lock on the path and a lock on the delayed ref head.
705 * We need both to get a consistent picture of how the refs look
706 * at a specified point in time
711 ret
= btrfs_search_slot(trans
, fs_info
->extent_root
, &key
, path
, 0, 0);
716 if (trans
!= BTRFS_BACKREF_SEARCH_COMMIT_ROOT
) {
718 * look if there are updates for this ref queued and lock the
721 delayed_refs
= &trans
->transaction
->delayed_refs
;
722 spin_lock(&delayed_refs
->lock
);
723 head
= btrfs_find_delayed_ref_head(trans
, bytenr
);
725 if (!mutex_trylock(&head
->mutex
)) {
726 atomic_inc(&head
->node
.refs
);
727 spin_unlock(&delayed_refs
->lock
);
729 btrfs_release_path(path
);
732 * Mutex was contended, block until it's
733 * released and try again
735 mutex_lock(&head
->mutex
);
736 mutex_unlock(&head
->mutex
);
737 btrfs_put_delayed_ref(&head
->node
);
740 ret
= __add_delayed_refs(head
, seq
, &prefs_delayed
);
742 spin_unlock(&delayed_refs
->lock
);
746 spin_unlock(&delayed_refs
->lock
);
749 if (path
->slots
[0]) {
750 struct extent_buffer
*leaf
;
754 leaf
= path
->nodes
[0];
755 slot
= path
->slots
[0];
756 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
757 if (key
.objectid
== bytenr
&&
758 key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
759 ret
= __add_inline_refs(fs_info
, path
, bytenr
,
760 &info_level
, &prefs
);
763 ret
= __add_keyed_refs(fs_info
, path
, bytenr
,
769 btrfs_release_path(path
);
771 list_splice_init(&prefs_delayed
, &prefs
);
773 ret
= __add_missing_keys(fs_info
, &prefs
);
777 ret
= __merge_refs(&prefs
, 1);
781 ret
= __resolve_indirect_refs(fs_info
, search_commit_root
, &prefs
);
785 ret
= __merge_refs(&prefs
, 2);
789 while (!list_empty(&prefs
)) {
790 ref
= list_first_entry(&prefs
, struct __prelim_ref
, list
);
791 list_del(&ref
->list
);
794 if (ref
->count
&& ref
->root_id
&& ref
->parent
== 0) {
795 /* no parent == root of tree */
796 ret
= ulist_add(roots
, ref
->root_id
, 0, GFP_NOFS
);
799 if (ref
->count
&& ref
->parent
) {
800 ret
= ulist_add(refs
, ref
->parent
, 0, GFP_NOFS
);
808 mutex_unlock(&head
->mutex
);
809 btrfs_free_path(path
);
810 while (!list_empty(&prefs
)) {
811 ref
= list_first_entry(&prefs
, struct __prelim_ref
, list
);
812 list_del(&ref
->list
);
815 while (!list_empty(&prefs_delayed
)) {
816 ref
= list_first_entry(&prefs_delayed
, struct __prelim_ref
,
818 list_del(&ref
->list
);
826 * Finds all leafs with a reference to the specified combination of bytenr and
827 * offset. key_list_head will point to a list of corresponding keys (caller must
828 * free each list element). The leafs will be stored in the leafs ulist, which
829 * must be freed with ulist_free.
831 * returns 0 on success, <0 on error
833 static int btrfs_find_all_leafs(struct btrfs_trans_handle
*trans
,
834 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
835 u64 num_bytes
, u64 seq
, struct ulist
**leafs
)
840 tmp
= ulist_alloc(GFP_NOFS
);
843 *leafs
= ulist_alloc(GFP_NOFS
);
849 ret
= find_parent_nodes(trans
, fs_info
, bytenr
, seq
, *leafs
, tmp
);
852 if (ret
< 0 && ret
!= -ENOENT
) {
861 * walk all backrefs for a given extent to find all roots that reference this
862 * extent. Walking a backref means finding all extents that reference this
863 * extent and in turn walk the backrefs of those, too. Naturally this is a
864 * recursive process, but here it is implemented in an iterative fashion: We
865 * find all referencing extents for the extent in question and put them on a
866 * list. In turn, we find all referencing extents for those, further appending
867 * to the list. The way we iterate the list allows adding more elements after
868 * the current while iterating. The process stops when we reach the end of the
869 * list. Found roots are added to the roots list.
871 * returns 0 on success, < 0 on error.
873 int btrfs_find_all_roots(struct btrfs_trans_handle
*trans
,
874 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
875 u64 num_bytes
, u64 seq
, struct ulist
**roots
)
878 struct ulist_node
*node
= NULL
;
879 struct ulist_iterator uiter
;
882 tmp
= ulist_alloc(GFP_NOFS
);
885 *roots
= ulist_alloc(GFP_NOFS
);
891 ULIST_ITER_INIT(&uiter
);
893 ret
= find_parent_nodes(trans
, fs_info
, bytenr
, seq
,
895 if (ret
< 0 && ret
!= -ENOENT
) {
900 node
= ulist_next(tmp
, &uiter
);
911 static int __inode_info(u64 inum
, u64 ioff
, u8 key_type
,
912 struct btrfs_root
*fs_root
, struct btrfs_path
*path
,
913 struct btrfs_key
*found_key
)
916 struct btrfs_key key
;
917 struct extent_buffer
*eb
;
923 ret
= btrfs_search_slot(NULL
, fs_root
, &key
, path
, 0, 0);
928 if (ret
&& path
->slots
[0] >= btrfs_header_nritems(eb
)) {
929 ret
= btrfs_next_leaf(fs_root
, path
);
935 btrfs_item_key_to_cpu(eb
, found_key
, path
->slots
[0]);
936 if (found_key
->type
!= key
.type
|| found_key
->objectid
!= key
.objectid
)
943 * this makes the path point to (inum INODE_ITEM ioff)
945 int inode_item_info(u64 inum
, u64 ioff
, struct btrfs_root
*fs_root
,
946 struct btrfs_path
*path
)
948 struct btrfs_key key
;
949 return __inode_info(inum
, ioff
, BTRFS_INODE_ITEM_KEY
, fs_root
, path
,
953 static int inode_ref_info(u64 inum
, u64 ioff
, struct btrfs_root
*fs_root
,
954 struct btrfs_path
*path
,
955 struct btrfs_key
*found_key
)
957 return __inode_info(inum
, ioff
, BTRFS_INODE_REF_KEY
, fs_root
, path
,
962 * this iterates to turn a btrfs_inode_ref into a full filesystem path. elements
963 * of the path are separated by '/' and the path is guaranteed to be
964 * 0-terminated. the path is only given within the current file system.
965 * Therefore, it never starts with a '/'. the caller is responsible to provide
966 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
967 * the start point of the resulting string is returned. this pointer is within
969 * in case the path buffer would overflow, the pointer is decremented further
970 * as if output was written to the buffer, though no more output is actually
971 * generated. that way, the caller can determine how much space would be
972 * required for the path to fit into the buffer. in that case, the returned
973 * value will be smaller than dest. callers must check this!
975 static char *iref_to_path(struct btrfs_root
*fs_root
, struct btrfs_path
*path
,
976 struct btrfs_inode_ref
*iref
,
977 struct extent_buffer
*eb_in
, u64 parent
,
978 char *dest
, u32 size
)
984 s64 bytes_left
= size
- 1;
985 struct extent_buffer
*eb
= eb_in
;
986 struct btrfs_key found_key
;
987 int leave_spinning
= path
->leave_spinning
;
990 dest
[bytes_left
] = '\0';
992 path
->leave_spinning
= 1;
994 len
= btrfs_inode_ref_name_len(eb
, iref
);
997 read_extent_buffer(eb
, dest
+ bytes_left
,
998 (unsigned long)(iref
+ 1), len
);
1000 btrfs_tree_read_unlock_blocking(eb
);
1001 free_extent_buffer(eb
);
1003 ret
= inode_ref_info(parent
, 0, fs_root
, path
, &found_key
);
1008 next_inum
= found_key
.offset
;
1010 /* regular exit ahead */
1011 if (parent
== next_inum
)
1014 slot
= path
->slots
[0];
1015 eb
= path
->nodes
[0];
1016 /* make sure we can use eb after releasing the path */
1018 atomic_inc(&eb
->refs
);
1019 btrfs_tree_read_lock(eb
);
1020 btrfs_set_lock_blocking_rw(eb
, BTRFS_READ_LOCK
);
1022 btrfs_release_path(path
);
1024 iref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
1027 if (bytes_left
>= 0)
1028 dest
[bytes_left
] = '/';
1031 btrfs_release_path(path
);
1032 path
->leave_spinning
= leave_spinning
;
1035 return ERR_PTR(ret
);
1037 return dest
+ bytes_left
;
1041 * this makes the path point to (logical EXTENT_ITEM *)
1042 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
1043 * tree blocks and <0 on error.
1045 int extent_from_logical(struct btrfs_fs_info
*fs_info
, u64 logical
,
1046 struct btrfs_path
*path
, struct btrfs_key
*found_key
)
1051 struct extent_buffer
*eb
;
1052 struct btrfs_extent_item
*ei
;
1053 struct btrfs_key key
;
1055 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
1056 key
.objectid
= logical
;
1057 key
.offset
= (u64
)-1;
1059 ret
= btrfs_search_slot(NULL
, fs_info
->extent_root
, &key
, path
, 0, 0);
1062 ret
= btrfs_previous_item(fs_info
->extent_root
, path
,
1063 0, BTRFS_EXTENT_ITEM_KEY
);
1067 btrfs_item_key_to_cpu(path
->nodes
[0], found_key
, path
->slots
[0]);
1068 if (found_key
->type
!= BTRFS_EXTENT_ITEM_KEY
||
1069 found_key
->objectid
> logical
||
1070 found_key
->objectid
+ found_key
->offset
<= logical
) {
1071 pr_debug("logical %llu is not within any extent\n",
1072 (unsigned long long)logical
);
1076 eb
= path
->nodes
[0];
1077 item_size
= btrfs_item_size_nr(eb
, path
->slots
[0]);
1078 BUG_ON(item_size
< sizeof(*ei
));
1080 ei
= btrfs_item_ptr(eb
, path
->slots
[0], struct btrfs_extent_item
);
1081 flags
= btrfs_extent_flags(eb
, ei
);
1083 pr_debug("logical %llu is at position %llu within the extent (%llu "
1084 "EXTENT_ITEM %llu) flags %#llx size %u\n",
1085 (unsigned long long)logical
,
1086 (unsigned long long)(logical
- found_key
->objectid
),
1087 (unsigned long long)found_key
->objectid
,
1088 (unsigned long long)found_key
->offset
,
1089 (unsigned long long)flags
, item_size
);
1090 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)
1091 return BTRFS_EXTENT_FLAG_TREE_BLOCK
;
1092 if (flags
& BTRFS_EXTENT_FLAG_DATA
)
1093 return BTRFS_EXTENT_FLAG_DATA
;
1099 * helper function to iterate extent inline refs. ptr must point to a 0 value
1100 * for the first call and may be modified. it is used to track state.
1101 * if more refs exist, 0 is returned and the next call to
1102 * __get_extent_inline_ref must pass the modified ptr parameter to get the
1103 * next ref. after the last ref was processed, 1 is returned.
1104 * returns <0 on error
1106 static int __get_extent_inline_ref(unsigned long *ptr
, struct extent_buffer
*eb
,
1107 struct btrfs_extent_item
*ei
, u32 item_size
,
1108 struct btrfs_extent_inline_ref
**out_eiref
,
1113 struct btrfs_tree_block_info
*info
;
1117 flags
= btrfs_extent_flags(eb
, ei
);
1118 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
) {
1119 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1121 (struct btrfs_extent_inline_ref
*)(info
+ 1);
1123 *out_eiref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
1125 *ptr
= (unsigned long)*out_eiref
;
1126 if ((void *)*ptr
>= (void *)ei
+ item_size
)
1130 end
= (unsigned long)ei
+ item_size
;
1131 *out_eiref
= (struct btrfs_extent_inline_ref
*)*ptr
;
1132 *out_type
= btrfs_extent_inline_ref_type(eb
, *out_eiref
);
1134 *ptr
+= btrfs_extent_inline_ref_size(*out_type
);
1135 WARN_ON(*ptr
> end
);
1137 return 1; /* last */
1143 * reads the tree block backref for an extent. tree level and root are returned
1144 * through out_level and out_root. ptr must point to a 0 value for the first
1145 * call and may be modified (see __get_extent_inline_ref comment).
1146 * returns 0 if data was provided, 1 if there was no more data to provide or
1149 int tree_backref_for_extent(unsigned long *ptr
, struct extent_buffer
*eb
,
1150 struct btrfs_extent_item
*ei
, u32 item_size
,
1151 u64
*out_root
, u8
*out_level
)
1155 struct btrfs_tree_block_info
*info
;
1156 struct btrfs_extent_inline_ref
*eiref
;
1158 if (*ptr
== (unsigned long)-1)
1162 ret
= __get_extent_inline_ref(ptr
, eb
, ei
, item_size
,
1167 if (type
== BTRFS_TREE_BLOCK_REF_KEY
||
1168 type
== BTRFS_SHARED_BLOCK_REF_KEY
)
1175 /* we can treat both ref types equally here */
1176 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1177 *out_root
= btrfs_extent_inline_ref_offset(eb
, eiref
);
1178 *out_level
= btrfs_tree_block_level(eb
, info
);
1181 *ptr
= (unsigned long)-1;
1186 static int iterate_leaf_refs(struct btrfs_fs_info
*fs_info
, u64 logical
,
1187 u64 orig_extent_item_objectid
,
1188 u64 extent_item_pos
, u64 root
,
1189 iterate_extent_inodes_t
*iterate
, void *ctx
)
1192 struct btrfs_key key
;
1193 struct btrfs_file_extent_item
*fi
;
1194 struct extent_buffer
*eb
;
1202 eb
= read_tree_block(fs_info
->tree_root
, logical
,
1203 fs_info
->tree_root
->leafsize
, 0);
1208 * from the shared data ref, we only have the leaf but we need
1209 * the key. thus, we must look into all items and see that we
1210 * find one (some) with a reference to our extent item.
1212 nritems
= btrfs_header_nritems(eb
);
1213 for (slot
= 0; slot
< nritems
; ++slot
) {
1214 btrfs_item_key_to_cpu(eb
, &key
, slot
);
1215 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
1217 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
1218 extent_type
= btrfs_file_extent_type(eb
, fi
);
1219 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
)
1221 /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
1222 disk_byte
= btrfs_file_extent_disk_bytenr(eb
, fi
);
1223 if (disk_byte
!= orig_extent_item_objectid
)
1226 data_offset
= btrfs_file_extent_offset(eb
, fi
);
1227 data_len
= btrfs_file_extent_num_bytes(eb
, fi
);
1229 if (extent_item_pos
< data_offset
||
1230 extent_item_pos
>= data_offset
+ data_len
)
1233 pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
1234 "root %llu\n", orig_extent_item_objectid
,
1235 key
.objectid
, key
.offset
, root
);
1236 ret
= iterate(key
.objectid
,
1237 key
.offset
+ (extent_item_pos
- data_offset
),
1240 pr_debug("stopping iteration because ret=%d\n", ret
);
1245 free_extent_buffer(eb
);
1251 * calls iterate() for every inode that references the extent identified by
1252 * the given parameters.
1253 * when the iterator function returns a non-zero value, iteration stops.
1255 int iterate_extent_inodes(struct btrfs_fs_info
*fs_info
,
1256 u64 extent_item_objectid
, u64 extent_item_pos
,
1257 int search_commit_root
,
1258 iterate_extent_inodes_t
*iterate
, void *ctx
)
1261 struct list_head data_refs
= LIST_HEAD_INIT(data_refs
);
1262 struct list_head shared_refs
= LIST_HEAD_INIT(shared_refs
);
1263 struct btrfs_trans_handle
*trans
;
1264 struct ulist
*refs
= NULL
;
1265 struct ulist
*roots
= NULL
;
1266 struct ulist_node
*ref_node
= NULL
;
1267 struct ulist_node
*root_node
= NULL
;
1268 struct seq_list seq_elem
;
1269 struct ulist_iterator ref_uiter
;
1270 struct ulist_iterator root_uiter
;
1271 struct btrfs_delayed_ref_root
*delayed_refs
= NULL
;
1273 pr_debug("resolving all inodes for extent %llu\n",
1274 extent_item_objectid
);
1276 if (search_commit_root
) {
1277 trans
= BTRFS_BACKREF_SEARCH_COMMIT_ROOT
;
1279 trans
= btrfs_join_transaction(fs_info
->extent_root
);
1281 return PTR_ERR(trans
);
1283 delayed_refs
= &trans
->transaction
->delayed_refs
;
1284 spin_lock(&delayed_refs
->lock
);
1285 btrfs_get_delayed_seq(delayed_refs
, &seq_elem
);
1286 spin_unlock(&delayed_refs
->lock
);
1289 ret
= btrfs_find_all_leafs(trans
, fs_info
, extent_item_objectid
,
1290 extent_item_pos
, seq_elem
.seq
,
1296 ULIST_ITER_INIT(&ref_uiter
);
1297 while (!ret
&& (ref_node
= ulist_next(refs
, &ref_uiter
))) {
1298 ret
= btrfs_find_all_roots(trans
, fs_info
, ref_node
->val
, -1,
1299 seq_elem
.seq
, &roots
);
1302 ULIST_ITER_INIT(&root_uiter
);
1303 while (!ret
&& (root_node
= ulist_next(roots
, &root_uiter
))) {
1304 pr_debug("root %llu references leaf %llu\n",
1305 root_node
->val
, ref_node
->val
);
1306 ret
= iterate_leaf_refs(fs_info
, ref_node
->val
,
1307 extent_item_objectid
,
1308 extent_item_pos
, root_node
->val
,
1316 if (!search_commit_root
) {
1317 btrfs_put_delayed_seq(delayed_refs
, &seq_elem
);
1318 btrfs_end_transaction(trans
, fs_info
->extent_root
);
1324 int iterate_inodes_from_logical(u64 logical
, struct btrfs_fs_info
*fs_info
,
1325 struct btrfs_path
*path
,
1326 iterate_extent_inodes_t
*iterate
, void *ctx
)
1329 u64 extent_item_pos
;
1330 struct btrfs_key found_key
;
1331 int search_commit_root
= path
->search_commit_root
;
1333 ret
= extent_from_logical(fs_info
, logical
, path
,
1335 btrfs_release_path(path
);
1336 if (ret
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)
1341 extent_item_pos
= logical
- found_key
.objectid
;
1342 ret
= iterate_extent_inodes(fs_info
, found_key
.objectid
,
1343 extent_item_pos
, search_commit_root
,
1349 static int iterate_irefs(u64 inum
, struct btrfs_root
*fs_root
,
1350 struct btrfs_path
*path
,
1351 iterate_irefs_t
*iterate
, void *ctx
)
1360 struct extent_buffer
*eb
;
1361 struct btrfs_item
*item
;
1362 struct btrfs_inode_ref
*iref
;
1363 struct btrfs_key found_key
;
1366 path
->leave_spinning
= 1;
1367 ret
= inode_ref_info(inum
, parent
? parent
+1 : 0, fs_root
, path
,
1372 ret
= found
? 0 : -ENOENT
;
1377 parent
= found_key
.offset
;
1378 slot
= path
->slots
[0];
1379 eb
= path
->nodes
[0];
1380 /* make sure we can use eb after releasing the path */
1381 atomic_inc(&eb
->refs
);
1382 btrfs_tree_read_lock(eb
);
1383 btrfs_set_lock_blocking_rw(eb
, BTRFS_READ_LOCK
);
1384 btrfs_release_path(path
);
1386 item
= btrfs_item_nr(eb
, slot
);
1387 iref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
1389 for (cur
= 0; cur
< btrfs_item_size(eb
, item
); cur
+= len
) {
1390 name_len
= btrfs_inode_ref_name_len(eb
, iref
);
1391 /* path must be released before calling iterate()! */
1392 pr_debug("following ref at offset %u for inode %llu in "
1394 (unsigned long long)found_key
.objectid
,
1395 (unsigned long long)fs_root
->objectid
);
1396 ret
= iterate(parent
, iref
, eb
, ctx
);
1399 len
= sizeof(*iref
) + name_len
;
1400 iref
= (struct btrfs_inode_ref
*)((char *)iref
+ len
);
1402 btrfs_tree_read_unlock_blocking(eb
);
1403 free_extent_buffer(eb
);
1406 btrfs_release_path(path
);
1412 * returns 0 if the path could be dumped (probably truncated)
1413 * returns <0 in case of an error
1415 static int inode_to_path(u64 inum
, struct btrfs_inode_ref
*iref
,
1416 struct extent_buffer
*eb
, void *ctx
)
1418 struct inode_fs_paths
*ipath
= ctx
;
1421 int i
= ipath
->fspath
->elem_cnt
;
1422 const int s_ptr
= sizeof(char *);
1425 bytes_left
= ipath
->fspath
->bytes_left
> s_ptr
?
1426 ipath
->fspath
->bytes_left
- s_ptr
: 0;
1428 fspath_min
= (char *)ipath
->fspath
->val
+ (i
+ 1) * s_ptr
;
1429 fspath
= iref_to_path(ipath
->fs_root
, ipath
->btrfs_path
, iref
, eb
,
1430 inum
, fspath_min
, bytes_left
);
1432 return PTR_ERR(fspath
);
1434 if (fspath
> fspath_min
) {
1435 pr_debug("path resolved: %s\n", fspath
);
1436 ipath
->fspath
->val
[i
] = (u64
)(unsigned long)fspath
;
1437 ++ipath
->fspath
->elem_cnt
;
1438 ipath
->fspath
->bytes_left
= fspath
- fspath_min
;
1440 pr_debug("missed path, not enough space. missing bytes: %lu, "
1441 "constructed so far: %s\n",
1442 (unsigned long)(fspath_min
- fspath
), fspath_min
);
1443 ++ipath
->fspath
->elem_missed
;
1444 ipath
->fspath
->bytes_missing
+= fspath_min
- fspath
;
1445 ipath
->fspath
->bytes_left
= 0;
1452 * this dumps all file system paths to the inode into the ipath struct, provided
1453 * is has been created large enough. each path is zero-terminated and accessed
1454 * from ipath->fspath->val[i].
1455 * when it returns, there are ipath->fspath->elem_cnt number of paths available
1456 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
1457 * number of missed paths in recored in ipath->fspath->elem_missed, otherwise,
1458 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
1459 * have been needed to return all paths.
1461 int paths_from_inode(u64 inum
, struct inode_fs_paths
*ipath
)
1463 return iterate_irefs(inum
, ipath
->fs_root
, ipath
->btrfs_path
,
1464 inode_to_path
, ipath
);
1467 struct btrfs_data_container
*init_data_container(u32 total_bytes
)
1469 struct btrfs_data_container
*data
;
1472 alloc_bytes
= max_t(size_t, total_bytes
, sizeof(*data
));
1473 data
= kmalloc(alloc_bytes
, GFP_NOFS
);
1475 return ERR_PTR(-ENOMEM
);
1477 if (total_bytes
>= sizeof(*data
)) {
1478 data
->bytes_left
= total_bytes
- sizeof(*data
);
1479 data
->bytes_missing
= 0;
1481 data
->bytes_missing
= sizeof(*data
) - total_bytes
;
1482 data
->bytes_left
= 0;
1486 data
->elem_missed
= 0;
1492 * allocates space to return multiple file system paths for an inode.
1493 * total_bytes to allocate are passed, note that space usable for actual path
1494 * information will be total_bytes - sizeof(struct inode_fs_paths).
1495 * the returned pointer must be freed with free_ipath() in the end.
1497 struct inode_fs_paths
*init_ipath(s32 total_bytes
, struct btrfs_root
*fs_root
,
1498 struct btrfs_path
*path
)
1500 struct inode_fs_paths
*ifp
;
1501 struct btrfs_data_container
*fspath
;
1503 fspath
= init_data_container(total_bytes
);
1505 return (void *)fspath
;
1507 ifp
= kmalloc(sizeof(*ifp
), GFP_NOFS
);
1510 return ERR_PTR(-ENOMEM
);
1513 ifp
->btrfs_path
= path
;
1514 ifp
->fspath
= fspath
;
1515 ifp
->fs_root
= fs_root
;
1520 void free_ipath(struct inode_fs_paths
*ipath
)
1524 kfree(ipath
->fspath
);