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
;
40 static int __add_prelim_ref(struct list_head
*head
, u64 root_id
,
41 struct btrfs_key
*key
, int level
, u64 parent
,
42 u64 wanted_disk_byte
, int count
)
44 struct __prelim_ref
*ref
;
46 /* in case we're adding delayed refs, we're holding the refs spinlock */
47 ref
= kmalloc(sizeof(*ref
), GFP_ATOMIC
);
51 ref
->root_id
= root_id
;
55 memset(&ref
->key
, 0, sizeof(ref
->key
));
60 ref
->wanted_disk_byte
= wanted_disk_byte
;
61 list_add_tail(&ref
->list
, head
);
66 static int add_all_parents(struct btrfs_root
*root
, struct btrfs_path
*path
,
67 struct ulist
*parents
,
68 struct extent_buffer
*eb
, int level
,
69 u64 wanted_objectid
, u64 wanted_disk_byte
)
73 struct btrfs_file_extent_item
*fi
;
78 ret
= ulist_add(parents
, eb
->start
, 0, GFP_NOFS
);
86 * if the current leaf is full with EXTENT_DATA items, we must
87 * check the next one if that holds a reference as well.
88 * ref->count cannot be used to skip this check.
89 * repeat this until we don't find any additional EXTENT_DATA items.
92 ret
= btrfs_next_leaf(root
, path
);
99 for (slot
= 0; slot
< btrfs_header_nritems(eb
); ++slot
) {
100 btrfs_item_key_to_cpu(eb
, &key
, slot
);
101 if (key
.objectid
!= wanted_objectid
||
102 key
.type
!= BTRFS_EXTENT_DATA_KEY
)
104 fi
= btrfs_item_ptr(eb
, slot
,
105 struct btrfs_file_extent_item
);
106 disk_byte
= btrfs_file_extent_disk_bytenr(eb
, fi
);
107 if (disk_byte
== wanted_disk_byte
)
116 * resolve an indirect backref in the form (root_id, key, level)
117 * to a logical address
119 static int __resolve_indirect_ref(struct btrfs_fs_info
*fs_info
,
120 int search_commit_root
,
121 struct __prelim_ref
*ref
,
122 struct ulist
*parents
)
124 struct btrfs_path
*path
;
125 struct btrfs_root
*root
;
126 struct btrfs_key root_key
;
127 struct btrfs_key key
= {0};
128 struct extent_buffer
*eb
;
131 int level
= ref
->level
;
133 path
= btrfs_alloc_path();
136 path
->search_commit_root
= !!search_commit_root
;
138 root_key
.objectid
= ref
->root_id
;
139 root_key
.type
= BTRFS_ROOT_ITEM_KEY
;
140 root_key
.offset
= (u64
)-1;
141 root
= btrfs_read_fs_root_no_name(fs_info
, &root_key
);
148 root_level
= btrfs_header_level(root
->node
);
151 if (root_level
+ 1 == level
)
154 path
->lowest_level
= level
;
155 ret
= btrfs_search_slot(NULL
, root
, &ref
->key
, path
, 0, 0);
156 pr_debug("search slot in root %llu (level %d, ref count %d) returned "
157 "%d for key (%llu %u %llu)\n",
158 (unsigned long long)ref
->root_id
, level
, ref
->count
, ret
,
159 (unsigned long long)ref
->key
.objectid
, ref
->key
.type
,
160 (unsigned long long)ref
->key
.offset
);
164 eb
= path
->nodes
[level
];
172 if (ret
== 1 && path
->slots
[0] >= btrfs_header_nritems(eb
)) {
173 ret
= btrfs_next_leaf(root
, path
);
179 btrfs_item_key_to_cpu(eb
, &key
, path
->slots
[0]);
182 /* the last two parameters will only be used for level == 0 */
183 ret
= add_all_parents(root
, path
, parents
, eb
, level
, key
.objectid
,
184 ref
->wanted_disk_byte
);
186 btrfs_free_path(path
);
191 * resolve all indirect backrefs from the list
193 static int __resolve_indirect_refs(struct btrfs_fs_info
*fs_info
,
194 int search_commit_root
,
195 struct list_head
*head
)
199 struct __prelim_ref
*ref
;
200 struct __prelim_ref
*ref_safe
;
201 struct __prelim_ref
*new_ref
;
202 struct ulist
*parents
;
203 struct ulist_node
*node
;
205 parents
= ulist_alloc(GFP_NOFS
);
210 * _safe allows us to insert directly after the current item without
211 * iterating over the newly inserted items.
212 * we're also allowed to re-assign ref during iteration.
214 list_for_each_entry_safe(ref
, ref_safe
, head
, list
) {
215 if (ref
->parent
) /* already direct */
219 err
= __resolve_indirect_ref(fs_info
, search_commit_root
,
227 /* we put the first parent into the ref at hand */
228 node
= ulist_next(parents
, NULL
);
229 ref
->parent
= node
? node
->val
: 0;
231 /* additional parents require new refs being added here */
232 while ((node
= ulist_next(parents
, node
))) {
233 new_ref
= kmalloc(sizeof(*new_ref
), GFP_NOFS
);
238 memcpy(new_ref
, ref
, sizeof(*ref
));
239 new_ref
->parent
= node
->val
;
240 list_add(&new_ref
->list
, &ref
->list
);
242 ulist_reinit(parents
);
250 * merge two lists of backrefs and adjust counts accordingly
252 * mode = 1: merge identical keys, if key is set
253 * mode = 2: merge identical parents
255 static int __merge_refs(struct list_head
*head
, int mode
)
257 struct list_head
*pos1
;
259 list_for_each(pos1
, head
) {
260 struct list_head
*n2
;
261 struct list_head
*pos2
;
262 struct __prelim_ref
*ref1
;
264 ref1
= list_entry(pos1
, struct __prelim_ref
, list
);
266 if (mode
== 1 && ref1
->key
.type
== 0)
268 for (pos2
= pos1
->next
, n2
= pos2
->next
; pos2
!= head
;
269 pos2
= n2
, n2
= pos2
->next
) {
270 struct __prelim_ref
*ref2
;
272 ref2
= list_entry(pos2
, struct __prelim_ref
, list
);
275 if (memcmp(&ref1
->key
, &ref2
->key
,
276 sizeof(ref1
->key
)) ||
277 ref1
->level
!= ref2
->level
||
278 ref1
->root_id
!= ref2
->root_id
)
280 ref1
->count
+= ref2
->count
;
282 if (ref1
->parent
!= ref2
->parent
)
284 ref1
->count
+= ref2
->count
;
286 list_del(&ref2
->list
);
295 * add all currently queued delayed refs from this head whose seq nr is
296 * smaller or equal that seq to the list
298 static int __add_delayed_refs(struct btrfs_delayed_ref_head
*head
, u64 seq
,
299 struct btrfs_key
*info_key
,
300 struct list_head
*prefs
)
302 struct btrfs_delayed_extent_op
*extent_op
= head
->extent_op
;
303 struct rb_node
*n
= &head
->node
.rb_node
;
307 if (extent_op
&& extent_op
->update_key
)
308 btrfs_disk_key_to_cpu(info_key
, &extent_op
->key
);
310 while ((n
= rb_prev(n
))) {
311 struct btrfs_delayed_ref_node
*node
;
312 node
= rb_entry(n
, struct btrfs_delayed_ref_node
,
314 if (node
->bytenr
!= head
->node
.bytenr
)
316 WARN_ON(node
->is_head
);
321 switch (node
->action
) {
322 case BTRFS_ADD_DELAYED_EXTENT
:
323 case BTRFS_UPDATE_DELAYED_HEAD
:
326 case BTRFS_ADD_DELAYED_REF
:
329 case BTRFS_DROP_DELAYED_REF
:
335 switch (node
->type
) {
336 case BTRFS_TREE_BLOCK_REF_KEY
: {
337 struct btrfs_delayed_tree_ref
*ref
;
339 ref
= btrfs_delayed_node_to_tree_ref(node
);
340 ret
= __add_prelim_ref(prefs
, ref
->root
, info_key
,
341 ref
->level
+ 1, 0, node
->bytenr
,
342 node
->ref_mod
* sgn
);
345 case BTRFS_SHARED_BLOCK_REF_KEY
: {
346 struct btrfs_delayed_tree_ref
*ref
;
348 ref
= btrfs_delayed_node_to_tree_ref(node
);
349 ret
= __add_prelim_ref(prefs
, ref
->root
, info_key
,
350 ref
->level
+ 1, ref
->parent
,
352 node
->ref_mod
* sgn
);
355 case BTRFS_EXTENT_DATA_REF_KEY
: {
356 struct btrfs_delayed_data_ref
*ref
;
357 struct btrfs_key key
;
359 ref
= btrfs_delayed_node_to_data_ref(node
);
361 key
.objectid
= ref
->objectid
;
362 key
.type
= BTRFS_EXTENT_DATA_KEY
;
363 key
.offset
= ref
->offset
;
364 ret
= __add_prelim_ref(prefs
, ref
->root
, &key
, 0, 0,
366 node
->ref_mod
* sgn
);
369 case BTRFS_SHARED_DATA_REF_KEY
: {
370 struct btrfs_delayed_data_ref
*ref
;
371 struct btrfs_key key
;
373 ref
= btrfs_delayed_node_to_data_ref(node
);
375 key
.objectid
= ref
->objectid
;
376 key
.type
= BTRFS_EXTENT_DATA_KEY
;
377 key
.offset
= ref
->offset
;
378 ret
= __add_prelim_ref(prefs
, ref
->root
, &key
, 0,
379 ref
->parent
, node
->bytenr
,
380 node
->ref_mod
* sgn
);
393 * add all inline backrefs for bytenr to the list
395 static int __add_inline_refs(struct btrfs_fs_info
*fs_info
,
396 struct btrfs_path
*path
, u64 bytenr
,
397 struct btrfs_key
*info_key
, int *info_level
,
398 struct list_head
*prefs
)
402 struct extent_buffer
*leaf
;
403 struct btrfs_key key
;
406 struct btrfs_extent_item
*ei
;
411 * enumerate all inline refs
413 leaf
= path
->nodes
[0];
414 slot
= path
->slots
[0] - 1;
416 item_size
= btrfs_item_size_nr(leaf
, slot
);
417 BUG_ON(item_size
< sizeof(*ei
));
419 ei
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_item
);
420 flags
= btrfs_extent_flags(leaf
, ei
);
422 ptr
= (unsigned long)(ei
+ 1);
423 end
= (unsigned long)ei
+ item_size
;
425 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
) {
426 struct btrfs_tree_block_info
*info
;
427 struct btrfs_disk_key disk_key
;
429 info
= (struct btrfs_tree_block_info
*)ptr
;
430 *info_level
= btrfs_tree_block_level(leaf
, info
);
431 btrfs_tree_block_key(leaf
, info
, &disk_key
);
432 btrfs_disk_key_to_cpu(info_key
, &disk_key
);
433 ptr
+= sizeof(struct btrfs_tree_block_info
);
436 BUG_ON(!(flags
& BTRFS_EXTENT_FLAG_DATA
));
440 struct btrfs_extent_inline_ref
*iref
;
444 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
445 type
= btrfs_extent_inline_ref_type(leaf
, iref
);
446 offset
= btrfs_extent_inline_ref_offset(leaf
, iref
);
449 case BTRFS_SHARED_BLOCK_REF_KEY
:
450 ret
= __add_prelim_ref(prefs
, 0, info_key
,
451 *info_level
+ 1, offset
,
454 case BTRFS_SHARED_DATA_REF_KEY
: {
455 struct btrfs_shared_data_ref
*sdref
;
458 sdref
= (struct btrfs_shared_data_ref
*)(iref
+ 1);
459 count
= btrfs_shared_data_ref_count(leaf
, sdref
);
460 ret
= __add_prelim_ref(prefs
, 0, NULL
, 0, offset
,
464 case BTRFS_TREE_BLOCK_REF_KEY
:
465 ret
= __add_prelim_ref(prefs
, offset
, info_key
,
466 *info_level
+ 1, 0, bytenr
, 1);
468 case BTRFS_EXTENT_DATA_REF_KEY
: {
469 struct btrfs_extent_data_ref
*dref
;
473 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
474 count
= btrfs_extent_data_ref_count(leaf
, dref
);
475 key
.objectid
= btrfs_extent_data_ref_objectid(leaf
,
477 key
.type
= BTRFS_EXTENT_DATA_KEY
;
478 key
.offset
= btrfs_extent_data_ref_offset(leaf
, dref
);
479 root
= btrfs_extent_data_ref_root(leaf
, dref
);
480 ret
= __add_prelim_ref(prefs
, root
, &key
, 0, 0, bytenr
,
488 ptr
+= btrfs_extent_inline_ref_size(type
);
495 * add all non-inline backrefs for bytenr to the list
497 static int __add_keyed_refs(struct btrfs_fs_info
*fs_info
,
498 struct btrfs_path
*path
, u64 bytenr
,
499 struct btrfs_key
*info_key
, int info_level
,
500 struct list_head
*prefs
)
502 struct btrfs_root
*extent_root
= fs_info
->extent_root
;
505 struct extent_buffer
*leaf
;
506 struct btrfs_key key
;
509 ret
= btrfs_next_item(extent_root
, path
);
517 slot
= path
->slots
[0];
518 leaf
= path
->nodes
[0];
519 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
521 if (key
.objectid
!= bytenr
)
523 if (key
.type
< BTRFS_TREE_BLOCK_REF_KEY
)
525 if (key
.type
> BTRFS_SHARED_DATA_REF_KEY
)
529 case BTRFS_SHARED_BLOCK_REF_KEY
:
530 ret
= __add_prelim_ref(prefs
, 0, info_key
,
531 info_level
+ 1, key
.offset
,
534 case BTRFS_SHARED_DATA_REF_KEY
: {
535 struct btrfs_shared_data_ref
*sdref
;
538 sdref
= btrfs_item_ptr(leaf
, slot
,
539 struct btrfs_shared_data_ref
);
540 count
= btrfs_shared_data_ref_count(leaf
, sdref
);
541 ret
= __add_prelim_ref(prefs
, 0, NULL
, 0, key
.offset
,
545 case BTRFS_TREE_BLOCK_REF_KEY
:
546 ret
= __add_prelim_ref(prefs
, key
.offset
, info_key
,
547 info_level
+ 1, 0, bytenr
, 1);
549 case BTRFS_EXTENT_DATA_REF_KEY
: {
550 struct btrfs_extent_data_ref
*dref
;
554 dref
= btrfs_item_ptr(leaf
, slot
,
555 struct btrfs_extent_data_ref
);
556 count
= btrfs_extent_data_ref_count(leaf
, dref
);
557 key
.objectid
= btrfs_extent_data_ref_objectid(leaf
,
559 key
.type
= BTRFS_EXTENT_DATA_KEY
;
560 key
.offset
= btrfs_extent_data_ref_offset(leaf
, dref
);
561 root
= btrfs_extent_data_ref_root(leaf
, dref
);
562 ret
= __add_prelim_ref(prefs
, root
, &key
, 0, 0,
576 * this adds all existing backrefs (inline backrefs, backrefs and delayed
577 * refs) for the given bytenr to the refs list, merges duplicates and resolves
578 * indirect refs to their parent bytenr.
579 * When roots are found, they're added to the roots list
581 * FIXME some caching might speed things up
583 static int find_parent_nodes(struct btrfs_trans_handle
*trans
,
584 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
585 u64 seq
, struct ulist
*refs
, struct ulist
*roots
)
587 struct btrfs_key key
;
588 struct btrfs_path
*path
;
589 struct btrfs_key info_key
= { 0 };
590 struct btrfs_delayed_ref_root
*delayed_refs
= NULL
;
591 struct btrfs_delayed_ref_head
*head
;
594 int search_commit_root
= (trans
== BTRFS_BACKREF_SEARCH_COMMIT_ROOT
);
595 struct list_head prefs_delayed
;
596 struct list_head prefs
;
597 struct __prelim_ref
*ref
;
599 INIT_LIST_HEAD(&prefs
);
600 INIT_LIST_HEAD(&prefs_delayed
);
602 key
.objectid
= bytenr
;
603 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
604 key
.offset
= (u64
)-1;
606 path
= btrfs_alloc_path();
609 path
->search_commit_root
= !!search_commit_root
;
612 * grab both a lock on the path and a lock on the delayed ref head.
613 * We need both to get a consistent picture of how the refs look
614 * at a specified point in time
619 ret
= btrfs_search_slot(trans
, fs_info
->extent_root
, &key
, path
, 0, 0);
624 if (trans
!= BTRFS_BACKREF_SEARCH_COMMIT_ROOT
) {
626 * look if there are updates for this ref queued and lock the
629 delayed_refs
= &trans
->transaction
->delayed_refs
;
630 spin_lock(&delayed_refs
->lock
);
631 head
= btrfs_find_delayed_ref_head(trans
, bytenr
);
633 if (!mutex_trylock(&head
->mutex
)) {
634 atomic_inc(&head
->node
.refs
);
635 spin_unlock(&delayed_refs
->lock
);
637 btrfs_release_path(path
);
640 * Mutex was contended, block until it's
641 * released and try again
643 mutex_lock(&head
->mutex
);
644 mutex_unlock(&head
->mutex
);
645 btrfs_put_delayed_ref(&head
->node
);
648 ret
= __add_delayed_refs(head
, seq
, &info_key
,
651 spin_unlock(&delayed_refs
->lock
);
655 spin_unlock(&delayed_refs
->lock
);
658 if (path
->slots
[0]) {
659 struct extent_buffer
*leaf
;
662 leaf
= path
->nodes
[0];
663 slot
= path
->slots
[0] - 1;
664 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
665 if (key
.objectid
== bytenr
&&
666 key
.type
== BTRFS_EXTENT_ITEM_KEY
) {
667 ret
= __add_inline_refs(fs_info
, path
, bytenr
,
668 &info_key
, &info_level
, &prefs
);
671 ret
= __add_keyed_refs(fs_info
, path
, bytenr
, &info_key
,
677 btrfs_release_path(path
);
680 * when adding the delayed refs above, the info_key might not have
681 * been known yet. Go over the list and replace the missing keys
683 list_for_each_entry(ref
, &prefs_delayed
, list
) {
684 if ((ref
->key
.offset
| ref
->key
.type
| ref
->key
.objectid
) == 0)
685 memcpy(&ref
->key
, &info_key
, sizeof(ref
->key
));
687 list_splice_init(&prefs_delayed
, &prefs
);
689 ret
= __merge_refs(&prefs
, 1);
693 ret
= __resolve_indirect_refs(fs_info
, search_commit_root
, &prefs
);
697 ret
= __merge_refs(&prefs
, 2);
701 while (!list_empty(&prefs
)) {
702 ref
= list_first_entry(&prefs
, struct __prelim_ref
, list
);
703 list_del(&ref
->list
);
706 if (ref
->count
&& ref
->root_id
&& ref
->parent
== 0) {
707 /* no parent == root of tree */
708 ret
= ulist_add(roots
, ref
->root_id
, 0, GFP_NOFS
);
711 if (ref
->count
&& ref
->parent
) {
712 ret
= ulist_add(refs
, ref
->parent
, 0, GFP_NOFS
);
720 mutex_unlock(&head
->mutex
);
721 btrfs_free_path(path
);
722 while (!list_empty(&prefs
)) {
723 ref
= list_first_entry(&prefs
, struct __prelim_ref
, list
);
724 list_del(&ref
->list
);
727 while (!list_empty(&prefs_delayed
)) {
728 ref
= list_first_entry(&prefs_delayed
, struct __prelim_ref
,
730 list_del(&ref
->list
);
738 * Finds all leafs with a reference to the specified combination of bytenr and
739 * offset. key_list_head will point to a list of corresponding keys (caller must
740 * free each list element). The leafs will be stored in the leafs ulist, which
741 * must be freed with ulist_free.
743 * returns 0 on success, <0 on error
745 static int btrfs_find_all_leafs(struct btrfs_trans_handle
*trans
,
746 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
747 u64 num_bytes
, u64 seq
, struct ulist
**leafs
)
752 tmp
= ulist_alloc(GFP_NOFS
);
755 *leafs
= ulist_alloc(GFP_NOFS
);
761 ret
= find_parent_nodes(trans
, fs_info
, bytenr
, seq
, *leafs
, tmp
);
764 if (ret
< 0 && ret
!= -ENOENT
) {
773 * walk all backrefs for a given extent to find all roots that reference this
774 * extent. Walking a backref means finding all extents that reference this
775 * extent and in turn walk the backrefs of those, too. Naturally this is a
776 * recursive process, but here it is implemented in an iterative fashion: We
777 * find all referencing extents for the extent in question and put them on a
778 * list. In turn, we find all referencing extents for those, further appending
779 * to the list. The way we iterate the list allows adding more elements after
780 * the current while iterating. The process stops when we reach the end of the
781 * list. Found roots are added to the roots list.
783 * returns 0 on success, < 0 on error.
785 int btrfs_find_all_roots(struct btrfs_trans_handle
*trans
,
786 struct btrfs_fs_info
*fs_info
, u64 bytenr
,
787 u64 num_bytes
, u64 seq
, struct ulist
**roots
)
790 struct ulist_node
*node
= NULL
;
793 tmp
= ulist_alloc(GFP_NOFS
);
796 *roots
= ulist_alloc(GFP_NOFS
);
803 ret
= find_parent_nodes(trans
, fs_info
, bytenr
, seq
,
805 if (ret
< 0 && ret
!= -ENOENT
) {
810 node
= ulist_next(tmp
, node
);
821 static int __inode_info(u64 inum
, u64 ioff
, u8 key_type
,
822 struct btrfs_root
*fs_root
, struct btrfs_path
*path
,
823 struct btrfs_key
*found_key
)
826 struct btrfs_key key
;
827 struct extent_buffer
*eb
;
833 ret
= btrfs_search_slot(NULL
, fs_root
, &key
, path
, 0, 0);
838 if (ret
&& path
->slots
[0] >= btrfs_header_nritems(eb
)) {
839 ret
= btrfs_next_leaf(fs_root
, path
);
845 btrfs_item_key_to_cpu(eb
, found_key
, path
->slots
[0]);
846 if (found_key
->type
!= key
.type
|| found_key
->objectid
!= key
.objectid
)
853 * this makes the path point to (inum INODE_ITEM ioff)
855 int inode_item_info(u64 inum
, u64 ioff
, struct btrfs_root
*fs_root
,
856 struct btrfs_path
*path
)
858 struct btrfs_key key
;
859 return __inode_info(inum
, ioff
, BTRFS_INODE_ITEM_KEY
, fs_root
, path
,
863 static int inode_ref_info(u64 inum
, u64 ioff
, struct btrfs_root
*fs_root
,
864 struct btrfs_path
*path
,
865 struct btrfs_key
*found_key
)
867 return __inode_info(inum
, ioff
, BTRFS_INODE_REF_KEY
, fs_root
, path
,
872 * this iterates to turn a btrfs_inode_ref into a full filesystem path. elements
873 * of the path are separated by '/' and the path is guaranteed to be
874 * 0-terminated. the path is only given within the current file system.
875 * Therefore, it never starts with a '/'. the caller is responsible to provide
876 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
877 * the start point of the resulting string is returned. this pointer is within
879 * in case the path buffer would overflow, the pointer is decremented further
880 * as if output was written to the buffer, though no more output is actually
881 * generated. that way, the caller can determine how much space would be
882 * required for the path to fit into the buffer. in that case, the returned
883 * value will be smaller than dest. callers must check this!
885 static char *iref_to_path(struct btrfs_root
*fs_root
, struct btrfs_path
*path
,
886 struct btrfs_inode_ref
*iref
,
887 struct extent_buffer
*eb_in
, u64 parent
,
888 char *dest
, u32 size
)
894 s64 bytes_left
= size
- 1;
895 struct extent_buffer
*eb
= eb_in
;
896 struct btrfs_key found_key
;
897 int leave_spinning
= path
->leave_spinning
;
900 dest
[bytes_left
] = '\0';
902 path
->leave_spinning
= 1;
904 len
= btrfs_inode_ref_name_len(eb
, iref
);
907 read_extent_buffer(eb
, dest
+ bytes_left
,
908 (unsigned long)(iref
+ 1), len
);
910 btrfs_tree_read_unlock_blocking(eb
);
911 free_extent_buffer(eb
);
913 ret
= inode_ref_info(parent
, 0, fs_root
, path
, &found_key
);
918 next_inum
= found_key
.offset
;
920 /* regular exit ahead */
921 if (parent
== next_inum
)
924 slot
= path
->slots
[0];
926 /* make sure we can use eb after releasing the path */
928 atomic_inc(&eb
->refs
);
929 btrfs_tree_read_lock(eb
);
930 btrfs_set_lock_blocking_rw(eb
, BTRFS_READ_LOCK
);
932 btrfs_release_path(path
);
934 iref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
938 dest
[bytes_left
] = '/';
941 btrfs_release_path(path
);
942 path
->leave_spinning
= leave_spinning
;
947 return dest
+ bytes_left
;
951 * this makes the path point to (logical EXTENT_ITEM *)
952 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
953 * tree blocks and <0 on error.
955 int extent_from_logical(struct btrfs_fs_info
*fs_info
, u64 logical
,
956 struct btrfs_path
*path
, struct btrfs_key
*found_key
)
961 struct extent_buffer
*eb
;
962 struct btrfs_extent_item
*ei
;
963 struct btrfs_key key
;
965 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
966 key
.objectid
= logical
;
967 key
.offset
= (u64
)-1;
969 ret
= btrfs_search_slot(NULL
, fs_info
->extent_root
, &key
, path
, 0, 0);
972 ret
= btrfs_previous_item(fs_info
->extent_root
, path
,
973 0, BTRFS_EXTENT_ITEM_KEY
);
977 btrfs_item_key_to_cpu(path
->nodes
[0], found_key
, path
->slots
[0]);
978 if (found_key
->type
!= BTRFS_EXTENT_ITEM_KEY
||
979 found_key
->objectid
> logical
||
980 found_key
->objectid
+ found_key
->offset
<= logical
) {
981 pr_debug("logical %llu is not within any extent\n",
982 (unsigned long long)logical
);
987 item_size
= btrfs_item_size_nr(eb
, path
->slots
[0]);
988 BUG_ON(item_size
< sizeof(*ei
));
990 ei
= btrfs_item_ptr(eb
, path
->slots
[0], struct btrfs_extent_item
);
991 flags
= btrfs_extent_flags(eb
, ei
);
993 pr_debug("logical %llu is at position %llu within the extent (%llu "
994 "EXTENT_ITEM %llu) flags %#llx size %u\n",
995 (unsigned long long)logical
,
996 (unsigned long long)(logical
- found_key
->objectid
),
997 (unsigned long long)found_key
->objectid
,
998 (unsigned long long)found_key
->offset
,
999 (unsigned long long)flags
, item_size
);
1000 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)
1001 return BTRFS_EXTENT_FLAG_TREE_BLOCK
;
1002 if (flags
& BTRFS_EXTENT_FLAG_DATA
)
1003 return BTRFS_EXTENT_FLAG_DATA
;
1009 * helper function to iterate extent inline refs. ptr must point to a 0 value
1010 * for the first call and may be modified. it is used to track state.
1011 * if more refs exist, 0 is returned and the next call to
1012 * __get_extent_inline_ref must pass the modified ptr parameter to get the
1013 * next ref. after the last ref was processed, 1 is returned.
1014 * returns <0 on error
1016 static int __get_extent_inline_ref(unsigned long *ptr
, struct extent_buffer
*eb
,
1017 struct btrfs_extent_item
*ei
, u32 item_size
,
1018 struct btrfs_extent_inline_ref
**out_eiref
,
1023 struct btrfs_tree_block_info
*info
;
1027 flags
= btrfs_extent_flags(eb
, ei
);
1028 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
) {
1029 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1031 (struct btrfs_extent_inline_ref
*)(info
+ 1);
1033 *out_eiref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
1035 *ptr
= (unsigned long)*out_eiref
;
1036 if ((void *)*ptr
>= (void *)ei
+ item_size
)
1040 end
= (unsigned long)ei
+ item_size
;
1041 *out_eiref
= (struct btrfs_extent_inline_ref
*)*ptr
;
1042 *out_type
= btrfs_extent_inline_ref_type(eb
, *out_eiref
);
1044 *ptr
+= btrfs_extent_inline_ref_size(*out_type
);
1045 WARN_ON(*ptr
> end
);
1047 return 1; /* last */
1053 * reads the tree block backref for an extent. tree level and root are returned
1054 * through out_level and out_root. ptr must point to a 0 value for the first
1055 * call and may be modified (see __get_extent_inline_ref comment).
1056 * returns 0 if data was provided, 1 if there was no more data to provide or
1059 int tree_backref_for_extent(unsigned long *ptr
, struct extent_buffer
*eb
,
1060 struct btrfs_extent_item
*ei
, u32 item_size
,
1061 u64
*out_root
, u8
*out_level
)
1065 struct btrfs_tree_block_info
*info
;
1066 struct btrfs_extent_inline_ref
*eiref
;
1068 if (*ptr
== (unsigned long)-1)
1072 ret
= __get_extent_inline_ref(ptr
, eb
, ei
, item_size
,
1077 if (type
== BTRFS_TREE_BLOCK_REF_KEY
||
1078 type
== BTRFS_SHARED_BLOCK_REF_KEY
)
1085 /* we can treat both ref types equally here */
1086 info
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1087 *out_root
= btrfs_extent_inline_ref_offset(eb
, eiref
);
1088 *out_level
= btrfs_tree_block_level(eb
, info
);
1091 *ptr
= (unsigned long)-1;
1096 static int iterate_leaf_refs(struct btrfs_fs_info
*fs_info
, u64 logical
,
1097 u64 orig_extent_item_objectid
,
1098 u64 extent_item_pos
, u64 root
,
1099 iterate_extent_inodes_t
*iterate
, void *ctx
)
1102 struct btrfs_key key
;
1103 struct btrfs_file_extent_item
*fi
;
1104 struct extent_buffer
*eb
;
1112 eb
= read_tree_block(fs_info
->tree_root
, logical
,
1113 fs_info
->tree_root
->leafsize
, 0);
1118 * from the shared data ref, we only have the leaf but we need
1119 * the key. thus, we must look into all items and see that we
1120 * find one (some) with a reference to our extent item.
1122 nritems
= btrfs_header_nritems(eb
);
1123 for (slot
= 0; slot
< nritems
; ++slot
) {
1124 btrfs_item_key_to_cpu(eb
, &key
, slot
);
1125 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
1127 fi
= btrfs_item_ptr(eb
, slot
, struct btrfs_file_extent_item
);
1128 extent_type
= btrfs_file_extent_type(eb
, fi
);
1129 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
)
1131 /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
1132 disk_byte
= btrfs_file_extent_disk_bytenr(eb
, fi
);
1133 if (disk_byte
!= orig_extent_item_objectid
)
1136 data_offset
= btrfs_file_extent_offset(eb
, fi
);
1137 data_len
= btrfs_file_extent_num_bytes(eb
, fi
);
1139 if (extent_item_pos
< data_offset
||
1140 extent_item_pos
>= data_offset
+ data_len
)
1143 pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
1144 "root %llu\n", orig_extent_item_objectid
,
1145 key
.objectid
, key
.offset
, root
);
1146 ret
= iterate(key
.objectid
,
1147 key
.offset
+ (extent_item_pos
- data_offset
),
1150 pr_debug("stopping iteration because ret=%d\n", ret
);
1155 free_extent_buffer(eb
);
1161 * calls iterate() for every inode that references the extent identified by
1162 * the given parameters.
1163 * when the iterator function returns a non-zero value, iteration stops.
1165 int iterate_extent_inodes(struct btrfs_fs_info
*fs_info
,
1166 u64 extent_item_objectid
, u64 extent_item_pos
,
1167 int search_commit_root
,
1168 iterate_extent_inodes_t
*iterate
, void *ctx
)
1171 struct list_head data_refs
= LIST_HEAD_INIT(data_refs
);
1172 struct list_head shared_refs
= LIST_HEAD_INIT(shared_refs
);
1173 struct btrfs_trans_handle
*trans
;
1174 struct ulist
*refs
= NULL
;
1175 struct ulist
*roots
= NULL
;
1176 struct ulist_node
*ref_node
= NULL
;
1177 struct ulist_node
*root_node
= NULL
;
1178 struct seq_list seq_elem
;
1179 struct btrfs_delayed_ref_root
*delayed_refs
= NULL
;
1181 pr_debug("resolving all inodes for extent %llu\n",
1182 extent_item_objectid
);
1184 if (search_commit_root
) {
1185 trans
= BTRFS_BACKREF_SEARCH_COMMIT_ROOT
;
1187 trans
= btrfs_join_transaction(fs_info
->extent_root
);
1189 return PTR_ERR(trans
);
1191 delayed_refs
= &trans
->transaction
->delayed_refs
;
1192 spin_lock(&delayed_refs
->lock
);
1193 btrfs_get_delayed_seq(delayed_refs
, &seq_elem
);
1194 spin_unlock(&delayed_refs
->lock
);
1197 ret
= btrfs_find_all_leafs(trans
, fs_info
, extent_item_objectid
,
1198 extent_item_pos
, seq_elem
.seq
,
1204 while (!ret
&& (ref_node
= ulist_next(refs
, ref_node
))) {
1205 ret
= btrfs_find_all_roots(trans
, fs_info
, ref_node
->val
, -1,
1206 seq_elem
.seq
, &roots
);
1209 while (!ret
&& (root_node
= ulist_next(roots
, root_node
))) {
1210 pr_debug("root %llu references leaf %llu\n",
1211 root_node
->val
, ref_node
->val
);
1212 ret
= iterate_leaf_refs(fs_info
, ref_node
->val
,
1213 extent_item_objectid
,
1214 extent_item_pos
, root_node
->val
,
1222 if (!search_commit_root
) {
1223 btrfs_put_delayed_seq(delayed_refs
, &seq_elem
);
1224 btrfs_end_transaction(trans
, fs_info
->extent_root
);
1230 int iterate_inodes_from_logical(u64 logical
, struct btrfs_fs_info
*fs_info
,
1231 struct btrfs_path
*path
,
1232 iterate_extent_inodes_t
*iterate
, void *ctx
)
1235 u64 extent_item_pos
;
1236 struct btrfs_key found_key
;
1237 int search_commit_root
= path
->search_commit_root
;
1239 ret
= extent_from_logical(fs_info
, logical
, path
,
1241 btrfs_release_path(path
);
1242 if (ret
& BTRFS_EXTENT_FLAG_TREE_BLOCK
)
1247 extent_item_pos
= logical
- found_key
.objectid
;
1248 ret
= iterate_extent_inodes(fs_info
, found_key
.objectid
,
1249 extent_item_pos
, search_commit_root
,
1255 static int iterate_irefs(u64 inum
, struct btrfs_root
*fs_root
,
1256 struct btrfs_path
*path
,
1257 iterate_irefs_t
*iterate
, void *ctx
)
1266 struct extent_buffer
*eb
;
1267 struct btrfs_item
*item
;
1268 struct btrfs_inode_ref
*iref
;
1269 struct btrfs_key found_key
;
1272 path
->leave_spinning
= 1;
1273 ret
= inode_ref_info(inum
, parent
? parent
+1 : 0, fs_root
, path
,
1278 ret
= found
? 0 : -ENOENT
;
1283 parent
= found_key
.offset
;
1284 slot
= path
->slots
[0];
1285 eb
= path
->nodes
[0];
1286 /* make sure we can use eb after releasing the path */
1287 atomic_inc(&eb
->refs
);
1288 btrfs_tree_read_lock(eb
);
1289 btrfs_set_lock_blocking_rw(eb
, BTRFS_READ_LOCK
);
1290 btrfs_release_path(path
);
1292 item
= btrfs_item_nr(eb
, slot
);
1293 iref
= btrfs_item_ptr(eb
, slot
, struct btrfs_inode_ref
);
1295 for (cur
= 0; cur
< btrfs_item_size(eb
, item
); cur
+= len
) {
1296 name_len
= btrfs_inode_ref_name_len(eb
, iref
);
1297 /* path must be released before calling iterate()! */
1298 pr_debug("following ref at offset %u for inode %llu in "
1300 (unsigned long long)found_key
.objectid
,
1301 (unsigned long long)fs_root
->objectid
);
1302 ret
= iterate(parent
, iref
, eb
, ctx
);
1305 len
= sizeof(*iref
) + name_len
;
1306 iref
= (struct btrfs_inode_ref
*)((char *)iref
+ len
);
1308 btrfs_tree_read_unlock_blocking(eb
);
1309 free_extent_buffer(eb
);
1312 btrfs_release_path(path
);
1318 * returns 0 if the path could be dumped (probably truncated)
1319 * returns <0 in case of an error
1321 static int inode_to_path(u64 inum
, struct btrfs_inode_ref
*iref
,
1322 struct extent_buffer
*eb
, void *ctx
)
1324 struct inode_fs_paths
*ipath
= ctx
;
1327 int i
= ipath
->fspath
->elem_cnt
;
1328 const int s_ptr
= sizeof(char *);
1331 bytes_left
= ipath
->fspath
->bytes_left
> s_ptr
?
1332 ipath
->fspath
->bytes_left
- s_ptr
: 0;
1334 fspath_min
= (char *)ipath
->fspath
->val
+ (i
+ 1) * s_ptr
;
1335 fspath
= iref_to_path(ipath
->fs_root
, ipath
->btrfs_path
, iref
, eb
,
1336 inum
, fspath_min
, bytes_left
);
1338 return PTR_ERR(fspath
);
1340 if (fspath
> fspath_min
) {
1341 pr_debug("path resolved: %s\n", fspath
);
1342 ipath
->fspath
->val
[i
] = (u64
)(unsigned long)fspath
;
1343 ++ipath
->fspath
->elem_cnt
;
1344 ipath
->fspath
->bytes_left
= fspath
- fspath_min
;
1346 pr_debug("missed path, not enough space. missing bytes: %lu, "
1347 "constructed so far: %s\n",
1348 (unsigned long)(fspath_min
- fspath
), fspath_min
);
1349 ++ipath
->fspath
->elem_missed
;
1350 ipath
->fspath
->bytes_missing
+= fspath_min
- fspath
;
1351 ipath
->fspath
->bytes_left
= 0;
1358 * this dumps all file system paths to the inode into the ipath struct, provided
1359 * is has been created large enough. each path is zero-terminated and accessed
1360 * from ipath->fspath->val[i].
1361 * when it returns, there are ipath->fspath->elem_cnt number of paths available
1362 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
1363 * number of missed paths in recored in ipath->fspath->elem_missed, otherwise,
1364 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
1365 * have been needed to return all paths.
1367 int paths_from_inode(u64 inum
, struct inode_fs_paths
*ipath
)
1369 return iterate_irefs(inum
, ipath
->fs_root
, ipath
->btrfs_path
,
1370 inode_to_path
, ipath
);
1373 struct btrfs_data_container
*init_data_container(u32 total_bytes
)
1375 struct btrfs_data_container
*data
;
1378 alloc_bytes
= max_t(size_t, total_bytes
, sizeof(*data
));
1379 data
= kmalloc(alloc_bytes
, GFP_NOFS
);
1381 return ERR_PTR(-ENOMEM
);
1383 if (total_bytes
>= sizeof(*data
)) {
1384 data
->bytes_left
= total_bytes
- sizeof(*data
);
1385 data
->bytes_missing
= 0;
1387 data
->bytes_missing
= sizeof(*data
) - total_bytes
;
1388 data
->bytes_left
= 0;
1392 data
->elem_missed
= 0;
1398 * allocates space to return multiple file system paths for an inode.
1399 * total_bytes to allocate are passed, note that space usable for actual path
1400 * information will be total_bytes - sizeof(struct inode_fs_paths).
1401 * the returned pointer must be freed with free_ipath() in the end.
1403 struct inode_fs_paths
*init_ipath(s32 total_bytes
, struct btrfs_root
*fs_root
,
1404 struct btrfs_path
*path
)
1406 struct inode_fs_paths
*ifp
;
1407 struct btrfs_data_container
*fspath
;
1409 fspath
= init_data_container(total_bytes
);
1411 return (void *)fspath
;
1413 ifp
= kmalloc(sizeof(*ifp
), GFP_NOFS
);
1416 return ERR_PTR(-ENOMEM
);
1419 ifp
->btrfs_path
= path
;
1420 ifp
->fspath
= fspath
;
1421 ifp
->fs_root
= fs_root
;
1426 void free_ipath(struct inode_fs_paths
*ipath
)
1430 kfree(ipath
->fspath
);