?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
btrfs-progs: check: move reada_walk_down to check/common.c
[btrfs-progs-unstable/devel.git] / backref.c
blob27309e07a1e99d07faff8d36e7fb3092616d17e0
1 /*
2 * Copyright (C) 2011 STRATO. All rights reserved.
3 *
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.
7 *
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.
12 *
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.
17 */
18
19 #include "kerncompat.h"
20 #include "ctree.h"
21 #include "disk-io.h"
22 #include "backref.h"
23 #include "kernel-shared/ulist.h"
24 #include "transaction.h"
25 #include "internal.h"
26
27 #define pr_debug(...) do { } while (0)
28
29 struct extent_inode_elem {
30 u64 inum;
31 u64 offset;
32 struct extent_inode_elem *next;
33 };
34
35 static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
36 struct btrfs_file_extent_item *fi,
37 u64 extent_item_pos,
38 struct extent_inode_elem **eie)
39 {
40 u64 offset = 0;
41 struct extent_inode_elem *e;
42
43 if (!btrfs_file_extent_compression(eb, fi) &&
44 !btrfs_file_extent_encryption(eb, fi) &&
45 !btrfs_file_extent_other_encoding(eb, fi)) {
46 u64 data_offset;
47 u64 data_len;
48
49 data_offset = btrfs_file_extent_offset(eb, fi);
50 data_len = btrfs_file_extent_num_bytes(eb, fi);
51
52 if (extent_item_pos < data_offset ||
53 extent_item_pos >= data_offset + data_len)
54 return 1;
55 offset = extent_item_pos - data_offset;
56 }
57
58 e = kmalloc(sizeof(*e), GFP_NOFS);
59 if (!e)
60 return -ENOMEM;
61
62 e->next = *eie;
63 e->inum = key->objectid;
64 e->offset = key->offset + offset;
65 *eie = e;
66
67 return 0;
68 }
69
70 static void free_inode_elem_list(struct extent_inode_elem *eie)
71 {
72 struct extent_inode_elem *eie_next;
73
74 for (; eie; eie = eie_next) {
75 eie_next = eie->next;
76 kfree(eie);
77 }
78 }
79
80 static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
81 u64 extent_item_pos,
82 struct extent_inode_elem **eie)
83 {
84 u64 disk_byte;
85 struct btrfs_key key;
86 struct btrfs_file_extent_item *fi;
87 int slot;
88 int nritems;
89 int extent_type;
90 int ret;
91
92 /*
93 * from the shared data ref, we only have the leaf but we need
94 * the key. thus, we must look into all items and see that we
95 * find one (some) with a reference to our extent item.
96 */
97 nritems = btrfs_header_nritems(eb);
98 for (slot = 0; slot < nritems; ++slot) {
99 btrfs_item_key_to_cpu(eb, &key, slot);
100 if (key.type != BTRFS_EXTENT_DATA_KEY)
101 continue;
102 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
103 extent_type = btrfs_file_extent_type(eb, fi);
104 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
105 continue;
106 /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
107 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
108 if (disk_byte != wanted_disk_byte)
109 continue;
110
111 ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
112 if (ret < 0)
113 return ret;
114 }
115
116 return 0;
117 }
118
119 /*
120 * this structure records all encountered refs on the way up to the root
121 */
122 struct __prelim_ref {
123 struct list_head list;
124 u64 root_id;
125 struct btrfs_key key_for_search;
126 int level;
127 int count;
128 struct extent_inode_elem *inode_list;
129 u64 parent;
130 u64 wanted_disk_byte;
131 };
132
133 static struct __prelim_ref *list_first_pref(struct list_head *head)
134 {
135 return list_first_entry(head, struct __prelim_ref, list);
136 }
137
138 struct pref_state {
139 struct list_head pending;
140 struct list_head pending_missing_keys;
141 struct list_head pending_indirect_refs;
142 };
143
144 static void init_pref_state(struct pref_state *prefstate)
145 {
146 INIT_LIST_HEAD(&prefstate->pending);
147 INIT_LIST_HEAD(&prefstate->pending_missing_keys);
148 INIT_LIST_HEAD(&prefstate->pending_indirect_refs);
149 }
150
151 /*
152 * the rules for all callers of this function are:
153 * - obtaining the parent is the goal
154 * - if you add a key, you must know that it is a correct key
155 * - if you cannot add the parent or a correct key, then we will look into the
156 * block later to set a correct key
157 *
158 * delayed refs
159 * ============
160 * backref type | shared | indirect | shared | indirect
161 * information | tree | tree | data | data
162 * --------------------+--------+----------+--------+----------
163 * parent logical | y | - | - | -
164 * key to resolve | - | y | y | y
165 * tree block logical | - | - | - | -
166 * root for resolving | y | y | y | y
167 *
168 * - column 1: we've the parent -> done
169 * - column 2, 3, 4: we use the key to find the parent
170 *
171 * on disk refs (inline or keyed)
172 * ==============================
173 * backref type | shared | indirect | shared | indirect
174 * information | tree | tree | data | data
175 * --------------------+--------+----------+--------+----------
176 * parent logical | y | - | y | -
177 * key to resolve | - | - | - | y
178 * tree block logical | y | y | y | y
179 * root for resolving | - | y | y | y
180 *
181 * - column 1, 3: we've the parent -> done
182 * - column 2: we take the first key from the block to find the parent
183 * (see __add_missing_keys)
184 * - column 4: we use the key to find the parent
185 *
186 * additional information that's available but not required to find the parent
187 * block might help in merging entries to gain some speed.
188 */
189
190 static int __add_prelim_ref(struct pref_state *prefstate, u64 root_id,
191 struct btrfs_key *key, int level,
192 u64 parent, u64 wanted_disk_byte, int count,
193 gfp_t gfp_mask)
194 {
195 struct list_head *head;
196 struct __prelim_ref *ref;
197
198 if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
199 return 0;
200
201 ref = kmalloc(sizeof(*ref), gfp_mask);
202 if (!ref)
203 return -ENOMEM;
204
205 ref->root_id = root_id;
206 if (key) {
207 ref->key_for_search = *key;
208 head = &prefstate->pending;
209 } else if (parent) {
210 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
211 head = &prefstate->pending;
212 } else {
213 memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
214 head = &prefstate->pending_missing_keys;
215 }
216
217 ref->inode_list = NULL;
218 ref->level = level;
219 ref->count = count;
220 ref->parent = parent;
221 ref->wanted_disk_byte = wanted_disk_byte;
222
223 list_add_tail(&ref->list, head);
224
225 return 0;
226 }
227
228 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
229 struct ulist *parents, struct __prelim_ref *ref,
230 int level, u64 time_seq, const u64 *extent_item_pos,
231 u64 total_refs)
232 {
233 int ret = 0;
234 int slot;
235 struct extent_buffer *eb;
236 struct btrfs_key key;
237 struct btrfs_key *key_for_search = &ref->key_for_search;
238 struct btrfs_file_extent_item *fi;
239 struct extent_inode_elem *eie = NULL, *old = NULL;
240 u64 disk_byte;
241 u64 wanted_disk_byte = ref->wanted_disk_byte;
242 u64 count = 0;
243
244 if (level != 0) {
245 eb = path->nodes[level];
246 ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
247 if (ret < 0)
248 return ret;
249 return 0;
250 }
251
252 /*
253 * We normally enter this function with the path already pointing to
254 * the first item to check. But sometimes, we may enter it with
255 * slot==nritems. In that case, go to the next leaf before we continue.
256 */
257 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
258 ret = btrfs_next_leaf(root, path);
259
260 while (!ret && count < total_refs) {
261 eb = path->nodes[0];
262 slot = path->slots[0];
263
264 btrfs_item_key_to_cpu(eb, &key, slot);
265
266 if (key.objectid != key_for_search->objectid ||
267 key.type != BTRFS_EXTENT_DATA_KEY)
268 break;
269
270 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
271 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
272
273 if (disk_byte == wanted_disk_byte) {
274 eie = NULL;
275 old = NULL;
276 count++;
277 if (extent_item_pos) {
278 ret = check_extent_in_eb(&key, eb, fi,
279 *extent_item_pos,
280 &eie);
281 if (ret < 0)
282 break;
283 }
284 if (ret > 0)
285 goto next;
286 ret = ulist_add_merge_ptr(parents, eb->start,
287 eie, (void **)&old, GFP_NOFS);
288 if (ret < 0)
289 break;
290 if (!ret && extent_item_pos) {
291 while (old->next)
292 old = old->next;
293 old->next = eie;
294 }
295 eie = NULL;
296 }
297 next:
298 ret = btrfs_next_item(root, path);
299 }
300
301 if (ret > 0)
302 ret = 0;
303 else if (ret < 0)
304 free_inode_elem_list(eie);
305 return ret;
306 }
307
308 /*
309 * resolve an indirect backref in the form (root_id, key, level)
310 * to a logical address
311 */
312 static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
313 struct btrfs_path *path, u64 time_seq,
314 struct __prelim_ref *ref,
315 struct ulist *parents,
316 const u64 *extent_item_pos, u64 total_refs)
317 {
318 struct btrfs_root *root;
319 struct btrfs_key root_key;
320 struct extent_buffer *eb;
321 int ret = 0;
322 int root_level;
323 int level = ref->level;
324
325 root_key.objectid = ref->root_id;
326 root_key.type = BTRFS_ROOT_ITEM_KEY;
327 root_key.offset = (u64)-1;
328
329 root = btrfs_read_fs_root(fs_info, &root_key);
330 if (IS_ERR(root)) {
331 ret = PTR_ERR(root);
332 goto out;
333 }
334
335 root_level = btrfs_root_level(&root->root_item);
336
337 if (root_level + 1 == level)
338 goto out;
339
340 path->lowest_level = level;
341 ret = btrfs_search_slot(NULL, root, &ref->key_for_search, path, 0, 0);
342
343 pr_debug("search slot in root %llu (level %d, ref count %d) returned "
344 "%d for key (%llu %u %llu)\n",
345 ref->root_id, level, ref->count, ret,
346 ref->key_for_search.objectid, ref->key_for_search.type,
347 ref->key_for_search.offset);
348 if (ret < 0)
349 goto out;
350
351 eb = path->nodes[level];
352 while (!eb) {
353 if (!level) {
354 ret = 1;
355 WARN_ON(1);
356 goto out;
357 }
358 level--;
359 eb = path->nodes[level];
360 }
361
362 ret = add_all_parents(root, path, parents, ref, level, time_seq,
363 extent_item_pos, total_refs);
364 out:
365 path->lowest_level = 0;
366 btrfs_release_path(path);
367 return ret;
368 }
369
370 /*
371 * resolve all indirect backrefs from the list
372 */
373 static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
374 struct pref_state *prefstate,
375 struct btrfs_path *path, u64 time_seq,
376 const u64 *extent_item_pos, u64 total_refs)
377 {
378 struct list_head *head = &prefstate->pending_indirect_refs;
379 int err;
380 int ret = 0;
381 struct __prelim_ref *ref;
382 struct __prelim_ref *new_ref;
383 struct ulist *parents;
384 struct ulist_node *node;
385 struct ulist_iterator uiter;
386
387 parents = ulist_alloc(GFP_NOFS);
388 if (!parents)
389 return -ENOMEM;
390
391 while (!list_empty(head)) {
392 ref = list_first_pref(head);
393 list_move(&ref->list, &prefstate->pending);
394 ASSERT(!ref->parent); /* already direct */
395 ASSERT(ref->count);
396 err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
397 parents, extent_item_pos,
398 total_refs);
399 /*
400 * we can only tolerate ENOENT,otherwise,we should catch error
401 * and return directly.
402 */
403 if (err == -ENOENT) {
404 continue;
405 } else if (err) {
406 ret = err;
407 goto out;
408 }
409
410 /* we put the first parent into the ref at hand */
411 ULIST_ITER_INIT(&uiter);
412 node = ulist_next(parents, &uiter);
413 ref->parent = node ? node->val : 0;
414 ref->inode_list = node ?
415 (struct extent_inode_elem *)(uintptr_t)node->aux : NULL;
416
417 /* additional parents require new refs being added here */
418 while ((node = ulist_next(parents, &uiter))) {
419 new_ref = kmalloc(sizeof(*new_ref), GFP_NOFS);
420 if (!new_ref) {
421 ret = -ENOMEM;
422 goto out;
423 }
424 memcpy(new_ref, ref, sizeof(*ref));
425 new_ref->parent = node->val;
426 new_ref->inode_list = (struct extent_inode_elem *)
427 (uintptr_t)node->aux;
428 list_add_tail(&new_ref->list, &prefstate->pending);
429 }
430 ulist_reinit(parents);
431 }
432 out:
433 ulist_free(parents);
434 return ret;
435 }
436
437 static inline int ref_for_same_block(struct __prelim_ref *ref1,
438 struct __prelim_ref *ref2)
439 {
440 if (ref1->level != ref2->level)
441 return 0;
442 if (ref1->root_id != ref2->root_id)
443 return 0;
444 if (ref1->key_for_search.type != ref2->key_for_search.type)
445 return 0;
446 if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
447 return 0;
448 if (ref1->key_for_search.offset != ref2->key_for_search.offset)
449 return 0;
450 if (ref1->parent != ref2->parent)
451 return 0;
452
453 return 1;
454 }
455
456 /*
457 * read tree blocks and add keys where required.
458 */
459 static int __add_missing_keys(struct btrfs_fs_info *fs_info,
460 struct pref_state *prefstate)
461 {
462 struct extent_buffer *eb;
463
464 while (!list_empty(&prefstate->pending_missing_keys)) {
465 struct __prelim_ref *ref;
466
467 ref = list_first_pref(&prefstate->pending_missing_keys);
468
469 ASSERT(ref->root_id);
470 ASSERT(!ref->parent);
471 ASSERT(!ref->key_for_search.type);
472 BUG_ON(!ref->wanted_disk_byte);
473 eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
474 if (!extent_buffer_uptodate(eb)) {
475 free_extent_buffer(eb);
476 return -EIO;
477 }
478 if (btrfs_header_level(eb) == 0)
479 btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
480 else
481 btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
482 free_extent_buffer(eb);
483 list_move(&ref->list, &prefstate->pending);
484 }
485 return 0;
486 }
487
488 /*
489 * merge two lists of backrefs and adjust counts accordingly
490 *
491 * mode = 1: merge identical keys, if key is set
492 * FIXME: if we add more keys in __add_prelim_ref, we can merge more here.
493 * additionally, we could even add a key range for the blocks we
494 * looked into to merge even more (-> replace unresolved refs by those
495 * having a parent).
496 * mode = 2: merge identical parents
497 */
498 static void __merge_refs(struct pref_state *prefstate, int mode)
499 {
500 struct list_head *head = &prefstate->pending;
501 struct list_head *pos1;
502
503 list_for_each(pos1, head) {
504 struct list_head *n2;
505 struct list_head *pos2;
506 struct __prelim_ref *ref1;
507
508 ref1 = list_entry(pos1, struct __prelim_ref, list);
509
510 for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
511 pos2 = n2, n2 = pos2->next) {
512 struct __prelim_ref *ref2;
513 struct __prelim_ref *xchg;
514 struct extent_inode_elem *eie;
515
516 ref2 = list_entry(pos2, struct __prelim_ref, list);
517
518 if (mode == 1) {
519 if (!ref_for_same_block(ref1, ref2))
520 continue;
521 if (!ref1->parent && ref2->parent) {
522 xchg = ref1;
523 ref1 = ref2;
524 ref2 = xchg;
525 }
526 } else {
527 if (ref1->parent != ref2->parent)
528 continue;
529 }
530
531 eie = ref1->inode_list;
532 while (eie && eie->next)
533 eie = eie->next;
534 if (eie)
535 eie->next = ref2->inode_list;
536 else
537 ref1->inode_list = ref2->inode_list;
538 ref1->count += ref2->count;
539
540 list_del(&ref2->list);
541 kfree(ref2);
542 }
543
544 }
545 }
546
547 /*
548 * add all inline backrefs for bytenr to the list
549 */
550 static int __add_inline_refs(struct btrfs_fs_info *fs_info,
551 struct pref_state *prefstate,
552 struct btrfs_path *path, u64 bytenr,
553 int *info_level, u64 *total_refs)
554 {
555 int ret = 0;
556 int slot;
557 struct extent_buffer *leaf;
558 struct btrfs_key key;
559 struct btrfs_key found_key;
560 unsigned long ptr;
561 unsigned long end;
562 struct btrfs_extent_item *ei;
563 u64 flags;
564 u64 item_size;
565 /*
566 * enumerate all inline refs
567 */
568 leaf = path->nodes[0];
569 slot = path->slots[0];
570
571 item_size = btrfs_item_size_nr(leaf, slot);
572 BUG_ON(item_size < sizeof(*ei));
573
574 ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
575 flags = btrfs_extent_flags(leaf, ei);
576 *total_refs += btrfs_extent_refs(leaf, ei);
577 btrfs_item_key_to_cpu(leaf, &found_key, slot);
578
579 ptr = (unsigned long)(ei + 1);
580 end = (unsigned long)ei + item_size;
581
582 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
583 flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
584 struct btrfs_tree_block_info *info;
585
586 info = (struct btrfs_tree_block_info *)ptr;
587 *info_level = btrfs_tree_block_level(leaf, info);
588 ptr += sizeof(struct btrfs_tree_block_info);
589 BUG_ON(ptr > end);
590 } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
591 *info_level = found_key.offset;
592 } else {
593 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
594 }
595
596 while (ptr < end) {
597 struct btrfs_extent_inline_ref *iref;
598 u64 offset;
599 int type;
600
601 iref = (struct btrfs_extent_inline_ref *)ptr;
602 type = btrfs_extent_inline_ref_type(leaf, iref);
603 offset = btrfs_extent_inline_ref_offset(leaf, iref);
604
605 switch (type) {
606 case BTRFS_SHARED_BLOCK_REF_KEY:
607 ret = __add_prelim_ref(prefstate, 0, NULL,
608 *info_level + 1, offset,
609 bytenr, 1, GFP_NOFS);
610 break;
611 case BTRFS_SHARED_DATA_REF_KEY: {
612 struct btrfs_shared_data_ref *sdref;
613 int count;
614
615 sdref = (struct btrfs_shared_data_ref *)(iref + 1);
616 count = btrfs_shared_data_ref_count(leaf, sdref);
617 ret = __add_prelim_ref(prefstate, 0, NULL, 0, offset,
618 bytenr, count, GFP_NOFS);
619 break;
620 }
621 case BTRFS_TREE_BLOCK_REF_KEY:
622 ret = __add_prelim_ref(prefstate, offset, NULL,
623 *info_level + 1, 0,
624 bytenr, 1, GFP_NOFS);
625 break;
626 case BTRFS_EXTENT_DATA_REF_KEY: {
627 struct btrfs_extent_data_ref *dref;
628 int count;
629 u64 root;
630
631 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
632 count = btrfs_extent_data_ref_count(leaf, dref);
633 key.objectid = btrfs_extent_data_ref_objectid(leaf,
634 dref);
635 key.type = BTRFS_EXTENT_DATA_KEY;
636 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
637 root = btrfs_extent_data_ref_root(leaf, dref);
638 ret = __add_prelim_ref(prefstate, root, &key, 0, 0,
639 bytenr, count, GFP_NOFS);
640 break;
641 }
642 default:
643 WARN_ON(1);
644 }
645 if (ret)
646 return ret;
647 ptr += btrfs_extent_inline_ref_size(type);
648 }
649
650 return 0;
651 }
652
653 /*
654 * add all non-inline backrefs for bytenr to the list
655 */
656 static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
657 struct pref_state *prefstate,
658 struct btrfs_path *path, u64 bytenr,
659 int info_level)
660 {
661 struct btrfs_root *extent_root = fs_info->extent_root;
662 int ret;
663 int slot;
664 struct extent_buffer *leaf;
665 struct btrfs_key key;
666
667 while (1) {
668 ret = btrfs_next_item(extent_root, path);
669 if (ret < 0)
670 break;
671 if (ret) {
672 ret = 0;
673 break;
674 }
675
676 slot = path->slots[0];
677 leaf = path->nodes[0];
678 btrfs_item_key_to_cpu(leaf, &key, slot);
679
680 if (key.objectid != bytenr)
681 break;
682 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
683 continue;
684 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
685 break;
686
687 switch (key.type) {
688 case BTRFS_SHARED_BLOCK_REF_KEY:
689 ret = __add_prelim_ref(prefstate, 0, NULL,
690 info_level + 1, key.offset,
691 bytenr, 1, GFP_NOFS);
692 break;
693 case BTRFS_SHARED_DATA_REF_KEY: {
694 struct btrfs_shared_data_ref *sdref;
695 int count;
696
697 sdref = btrfs_item_ptr(leaf, slot,
698 struct btrfs_shared_data_ref);
699 count = btrfs_shared_data_ref_count(leaf, sdref);
700 ret = __add_prelim_ref(prefstate, 0, NULL, 0, key.offset,
701 bytenr, count, GFP_NOFS);
702 break;
703 }
704 case BTRFS_TREE_BLOCK_REF_KEY:
705 ret = __add_prelim_ref(prefstate, key.offset, NULL,
706 info_level + 1, 0,
707 bytenr, 1, GFP_NOFS);
708 break;
709 case BTRFS_EXTENT_DATA_REF_KEY: {
710 struct btrfs_extent_data_ref *dref;
711 int count;
712 u64 root;
713
714 dref = btrfs_item_ptr(leaf, slot,
715 struct btrfs_extent_data_ref);
716 count = btrfs_extent_data_ref_count(leaf, dref);
717 key.objectid = btrfs_extent_data_ref_objectid(leaf,
718 dref);
719 key.type = BTRFS_EXTENT_DATA_KEY;
720 key.offset = btrfs_extent_data_ref_offset(leaf, dref);
721 root = btrfs_extent_data_ref_root(leaf, dref);
722 ret = __add_prelim_ref(prefstate, root, &key, 0, 0,
723 bytenr, count, GFP_NOFS);
724 break;
725 }
726 default:
727 WARN_ON(1);
728 }
729 if (ret)
730 return ret;
731
732 }
733
734 return ret;
735 }
736
737 /*
738 * this adds all existing backrefs (inline backrefs, backrefs and delayed
739 * refs) for the given bytenr to the refs list, merges duplicates and resolves
740 * indirect refs to their parent bytenr.
741 * When roots are found, they're added to the roots list
742 *
743 * FIXME some caching might speed things up
744 */
745 static int find_parent_nodes(struct btrfs_trans_handle *trans,
746 struct btrfs_fs_info *fs_info, u64 bytenr,
747 u64 time_seq, struct ulist *refs,
748 struct ulist *roots, const u64 *extent_item_pos)
749 {
750 struct btrfs_key key;
751 struct btrfs_path *path;
752 int info_level = 0;
753 int ret;
754 struct pref_state prefstate;
755 struct __prelim_ref *ref;
756 struct extent_inode_elem *eie = NULL;
757 u64 total_refs = 0;
758
759 init_pref_state(&prefstate);
760
761 key.objectid = bytenr;
762 key.offset = (u64)-1;
763 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
764 key.type = BTRFS_METADATA_ITEM_KEY;
765 else
766 key.type = BTRFS_EXTENT_ITEM_KEY;
767
768 path = btrfs_alloc_path();
769 if (!path)
770 return -ENOMEM;
771
772 ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
773 if (ret < 0)
774 goto out;
775 BUG_ON(ret == 0);
776
777 if (path->slots[0]) {
778 struct extent_buffer *leaf;
779 int slot;
780
781 path->slots[0]--;
782 leaf = path->nodes[0];
783 slot = path->slots[0];
784 btrfs_item_key_to_cpu(leaf, &key, slot);
785 if (key.objectid == bytenr &&
786 (key.type == BTRFS_EXTENT_ITEM_KEY ||
787 key.type == BTRFS_METADATA_ITEM_KEY)) {
788 ret = __add_inline_refs(fs_info, &prefstate, path,
789 bytenr, &info_level,
790 &total_refs);
791 if (ret)
792 goto out;
793 ret = __add_keyed_refs(fs_info, &prefstate, path,
794 bytenr, info_level);
795 if (ret)
796 goto out;
797 }
798 }
799 btrfs_release_path(path);
800
801 ret = __add_missing_keys(fs_info, &prefstate);
802 if (ret)
803 goto out;
804
805 __merge_refs(&prefstate, 1);
806
807 ret = __resolve_indirect_refs(fs_info, &prefstate, path, time_seq,
808 extent_item_pos, total_refs);
809 if (ret)
810 goto out;
811
812 __merge_refs(&prefstate, 2);
813
814 BUG_ON(!list_empty(&prefstate.pending_missing_keys));
815 BUG_ON(!list_empty(&prefstate.pending_indirect_refs));
816
817 while (!list_empty(&prefstate.pending)) {
818 ref = list_first_pref(&prefstate.pending);
819 WARN_ON(ref->count < 0);
820 if (roots && ref->count && ref->root_id && ref->parent == 0) {
821 /* no parent == root of tree */
822 ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
823 if (ret < 0)
824 goto out;
825 }
826 if (ref->count && ref->parent) {
827 if (extent_item_pos && !ref->inode_list &&
828 ref->level == 0) {
829 struct extent_buffer *eb;
830
831 eb = read_tree_block(fs_info, ref->parent, 0);
832 if (!extent_buffer_uptodate(eb)) {
833 free_extent_buffer(eb);
834 ret = -EIO;
835 goto out;
836 }
837 ret = find_extent_in_eb(eb, bytenr,
838 *extent_item_pos, &eie);
839 free_extent_buffer(eb);
840 if (ret < 0)
841 goto out;
842 ref->inode_list = eie;
843 }
844 ret = ulist_add_merge_ptr(refs, ref->parent,
845 ref->inode_list,
846 (void **)&eie, GFP_NOFS);
847 if (ret < 0)
848 goto out;
849 if (!ret && extent_item_pos) {
850 /*
851 * we've recorded that parent, so we must extend
852 * its inode list here
853 */
854 BUG_ON(!eie);
855 while (eie->next)
856 eie = eie->next;
857 eie->next = ref->inode_list;
858 }
859 eie = NULL;
860 }
861 list_del(&ref->list);
862 kfree(ref);
863 }
864
865 out:
866 btrfs_free_path(path);
867 while (!list_empty(&prefstate.pending)) {
868 ref = list_first_pref(&prefstate.pending);
869 list_del(&ref->list);
870 kfree(ref);
871 }
872 if (ret < 0)
873 free_inode_elem_list(eie);
874 return ret;
875 }
876
877 static void free_leaf_list(struct ulist *blocks)
878 {
879 struct ulist_node *node = NULL;
880 struct extent_inode_elem *eie;
881 struct ulist_iterator uiter;
882
883 ULIST_ITER_INIT(&uiter);
884 while ((node = ulist_next(blocks, &uiter))) {
885 if (!node->aux)
886 continue;
887 eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
888 free_inode_elem_list(eie);
889 node->aux = 0;
890 }
891
892 ulist_free(blocks);
893 }
894
895 /*
896 * Finds all leafs with a reference to the specified combination of bytenr and
897 * offset. key_list_head will point to a list of corresponding keys (caller must
898 * free each list element). The leafs will be stored in the leafs ulist, which
899 * must be freed with ulist_free.
900 *
901 * returns 0 on success, <0 on error
902 */
903 static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
904 struct btrfs_fs_info *fs_info, u64 bytenr,
905 u64 time_seq, struct ulist **leafs,
906 const u64 *extent_item_pos)
907 {
908 int ret;
909
910 *leafs = ulist_alloc(GFP_NOFS);
911 if (!*leafs)
912 return -ENOMEM;
913
914 ret = find_parent_nodes(trans, fs_info, bytenr,
915 time_seq, *leafs, NULL, extent_item_pos);
916 if (ret < 0 && ret != -ENOENT) {
917 free_leaf_list(*leafs);
918 return ret;
919 }
920
921 return 0;
922 }
923
924 /*
925 * walk all backrefs for a given extent to find all roots that reference this
926 * extent. Walking a backref means finding all extents that reference this
927 * extent and in turn walk the backrefs of those, too. Naturally this is a
928 * recursive process, but here it is implemented in an iterative fashion: We
929 * find all referencing extents for the extent in question and put them on a
930 * list. In turn, we find all referencing extents for those, further appending
931 * to the list. The way we iterate the list allows adding more elements after
932 * the current while iterating. The process stops when we reach the end of the
933 * list. Found roots are added to the roots list.
934 *
935 * returns 0 on success, < 0 on error.
936 */
937 static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
938 struct btrfs_fs_info *fs_info, u64 bytenr,
939 u64 time_seq, struct ulist **roots)
940 {
941 struct ulist *tmp;
942 struct ulist_node *node = NULL;
943 struct ulist_iterator uiter;
944 int ret;
945
946 tmp = ulist_alloc(GFP_NOFS);
947 if (!tmp)
948 return -ENOMEM;
949 *roots = ulist_alloc(GFP_NOFS);
950 if (!*roots) {
951 ulist_free(tmp);
952 return -ENOMEM;
953 }
954
955 ULIST_ITER_INIT(&uiter);
956 while (1) {
957 ret = find_parent_nodes(trans, fs_info, bytenr,
958 time_seq, tmp, *roots, NULL);
959 if (ret < 0 && ret != -ENOENT) {
960 ulist_free(tmp);
961 ulist_free(*roots);
962 return ret;
963 }
964 node = ulist_next(tmp, &uiter);
965 if (!node)
966 break;
967 bytenr = node->val;
968 cond_resched();
969 }
970
971 ulist_free(tmp);
972 return 0;
973 }
974
975 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
976 struct btrfs_fs_info *fs_info, u64 bytenr,
977 u64 time_seq, struct ulist **roots)
978 {
979 return __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
980 }
981
982 /*
983 * this makes the path point to (inum INODE_ITEM ioff)
984 */
985 int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
986 struct btrfs_path *path)
987 {
988 struct btrfs_key key;
989 return btrfs_find_item(fs_root, path, inum, ioff,
990 BTRFS_INODE_ITEM_KEY, &key);
991 }
992
993 static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
994 struct btrfs_path *path,
995 struct btrfs_key *found_key)
996 {
997 return btrfs_find_item(fs_root, path, inum, ioff,
998 BTRFS_INODE_REF_KEY, found_key);
999 }
1000
1001 int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
1002 u64 start_off, struct btrfs_path *path,
1003 struct btrfs_inode_extref **ret_extref,
1004 u64 *found_off)
1005 {
1006 int ret, slot;
1007 struct btrfs_key key;
1008 struct btrfs_key found_key;
1009 struct btrfs_inode_extref *extref;
1010 struct extent_buffer *leaf;
1011 unsigned long ptr;
1012
1013 key.objectid = inode_objectid;
1014 key.type = BTRFS_INODE_EXTREF_KEY;
1015 key.offset = start_off;
1016
1017 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1018 if (ret < 0)
1019 return ret;
1020
1021 while (1) {
1022 leaf = path->nodes[0];
1023 slot = path->slots[0];
1024 if (slot >= btrfs_header_nritems(leaf)) {
1025 /*
1026 * If the item at offset is not found,
1027 * btrfs_search_slot will point us to the slot
1028 * where it should be inserted. In our case
1029 * that will be the slot directly before the
1030 * next INODE_REF_KEY_V2 item. In the case
1031 * that we're pointing to the last slot in a
1032 * leaf, we must move one leaf over.
1033 */
1034 ret = btrfs_next_leaf(root, path);
1035 if (ret) {
1036 if (ret >= 1)
1037 ret = -ENOENT;
1038 break;
1039 }
1040 continue;
1041 }
1042
1043 btrfs_item_key_to_cpu(leaf, &found_key, slot);
1044
1045 /*
1046 * Check that we're still looking at an extended ref key for
1047 * this particular objectid. If we have different
1048 * objectid or type then there are no more to be found
1049 * in the tree and we can exit.
1050 */
1051 ret = -ENOENT;
1052 if (found_key.objectid != inode_objectid)
1053 break;
1054 if (found_key.type != BTRFS_INODE_EXTREF_KEY)
1055 break;
1056
1057 ret = 0;
1058 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1059 extref = (struct btrfs_inode_extref *)ptr;
1060 *ret_extref = extref;
1061 if (found_off)
1062 *found_off = found_key.offset;
1063 break;
1064 }
1065
1066 return ret;
1067 }
1068
1069 /*
1070 * this iterates to turn a name (from iref/extref) into a full filesystem path.
1071 * Elements of the path are separated by '/' and the path is guaranteed to be
1072 * 0-terminated. the path is only given within the current file system.
1073 * Therefore, it never starts with a '/'. the caller is responsible to provide
1074 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
1075 * the start point of the resulting string is returned. this pointer is within
1076 * dest, normally.
1077 * in case the path buffer would overflow, the pointer is decremented further
1078 * as if output was written to the buffer, though no more output is actually
1079 * generated. that way, the caller can determine how much space would be
1080 * required for the path to fit into the buffer. in that case, the returned
1081 * value will be smaller than dest. callers must check this!
1082 */
1083 char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
1084 u32 name_len, unsigned long name_off,
1085 struct extent_buffer *eb_in, u64 parent,
1086 char *dest, u32 size)
1087 {
1088 int slot;
1089 u64 next_inum;
1090 int ret;
1091 s64 bytes_left = ((s64)size) - 1;
1092 struct extent_buffer *eb = eb_in;
1093 struct btrfs_key found_key;
1094 struct btrfs_inode_ref *iref;
1095
1096 if (bytes_left >= 0)
1097 dest[bytes_left] = '\0';
1098
1099 while (1) {
1100 bytes_left -= name_len;
1101 if (bytes_left >= 0)
1102 read_extent_buffer(eb, dest + bytes_left,
1103 name_off, name_len);
1104 if (eb != eb_in)
1105 free_extent_buffer(eb);
1106 ret = inode_ref_info(parent, 0, fs_root, path, &found_key);
1107 if (ret > 0)
1108 ret = -ENOENT;
1109 if (ret)
1110 break;
1111
1112 next_inum = found_key.offset;
1113
1114 /* regular exit ahead */
1115 if (parent == next_inum)
1116 break;
1117
1118 slot = path->slots[0];
1119 eb = path->nodes[0];
1120 /* make sure we can use eb after releasing the path */
1121 if (eb != eb_in)
1122 eb->refs++;
1123 btrfs_release_path(path);
1124 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1125
1126 name_len = btrfs_inode_ref_name_len(eb, iref);
1127 name_off = (unsigned long)(iref + 1);
1128
1129 parent = next_inum;
1130 --bytes_left;
1131 if (bytes_left >= 0)
1132 dest[bytes_left] = '/';
1133 }
1134
1135 btrfs_release_path(path);
1136
1137 if (ret)
1138 return ERR_PTR(ret);
1139
1140 return dest + bytes_left;
1141 }
1142
1143 /*
1144 * this makes the path point to (logical EXTENT_ITEM *)
1145 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
1146 * tree blocks and <0 on error.
1147 */
1148 int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1149 struct btrfs_path *path, struct btrfs_key *found_key,
1150 u64 *flags_ret)
1151 {
1152 int ret;
1153 u64 flags;
1154 u64 size = 0;
1155 u32 item_size;
1156 struct extent_buffer *eb;
1157 struct btrfs_extent_item *ei;
1158 struct btrfs_key key;
1159
1160 if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1161 key.type = BTRFS_METADATA_ITEM_KEY;
1162 else
1163 key.type = BTRFS_EXTENT_ITEM_KEY;
1164 key.objectid = logical;
1165 key.offset = (u64)-1;
1166
1167 ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1168 if (ret < 0)
1169 return ret;
1170
1171 ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
1172 if (ret) {
1173 if (ret > 0)
1174 ret = -ENOENT;
1175 return ret;
1176 }
1177 btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1178 if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1179 size = fs_info->nodesize;
1180 else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
1181 size = found_key->offset;
1182
1183 if (found_key->objectid > logical ||
1184 found_key->objectid + size <= logical) {
1185 pr_debug("logical %llu is not within any extent\n", logical);
1186 return -ENOENT;
1187 }
1188
1189 eb = path->nodes[0];
1190 item_size = btrfs_item_size_nr(eb, path->slots[0]);
1191 BUG_ON(item_size < sizeof(*ei));
1192
1193 ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
1194 flags = btrfs_extent_flags(eb, ei);
1195
1196 pr_debug("logical %llu is at position %llu within the extent (%llu "
1197 "EXTENT_ITEM %llu) flags %#llx size %u\n",
1198 logical, logical - found_key->objectid, found_key->objectid,
1199 found_key->offset, flags, item_size);
1200
1201 if (flags_ret) {
1202 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1203 *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
1204 else if (flags & BTRFS_EXTENT_FLAG_DATA)
1205 *flags_ret = BTRFS_EXTENT_FLAG_DATA;
1206 else
1207 BUG_ON(1);
1208 return 0;
1209 } else {
1210 WARN_ON(1);
1211 return -EIO;
1212 }
1213 }
1214
1215 /*
1216 * helper function to iterate extent inline refs. ptr must point to a 0 value
1217 * for the first call and may be modified. it is used to track state.
1218 * if more refs exist, 0 is returned and the next call to
1219 * __get_extent_inline_ref must pass the modified ptr parameter to get the
1220 * next ref. after the last ref was processed, 1 is returned.
1221 * returns <0 on error
1222 */
1223 static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
1224 struct btrfs_key *key,
1225 struct btrfs_extent_item *ei, u32 item_size,
1226 struct btrfs_extent_inline_ref **out_eiref,
1227 int *out_type)
1228 {
1229 unsigned long end;
1230 u64 flags;
1231 struct btrfs_tree_block_info *info;
1232
1233 if (!*ptr) {
1234 /* first call */
1235 flags = btrfs_extent_flags(eb, ei);
1236 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1237 if (key->type == BTRFS_METADATA_ITEM_KEY) {
1238 /* a skinny metadata extent */
1239 *out_eiref =
1240 (struct btrfs_extent_inline_ref *)(ei + 1);
1241 } else {
1242 WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);
1243 info = (struct btrfs_tree_block_info *)(ei + 1);
1244 *out_eiref =
1245 (struct btrfs_extent_inline_ref *)(info + 1);
1246 }
1247 } else {
1248 *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
1249 }
1250 *ptr = (unsigned long)*out_eiref;
1251 if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
1252 return -ENOENT;
1253 }
1254
1255 end = (unsigned long)ei + item_size;
1256 *out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
1257 *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);
1258
1259 *ptr += btrfs_extent_inline_ref_size(*out_type);
1260 WARN_ON(*ptr > end);
1261 if (*ptr == end)
1262 return 1; /* last */
1263
1264 return 0;
1265 }
1266
1267 /*
1268 * reads the tree block backref for an extent. tree level and root are returned
1269 * through out_level and out_root. ptr must point to a 0 value for the first
1270 * call and may be modified (see __get_extent_inline_ref comment).
1271 * returns 0 if data was provided, 1 if there was no more data to provide or
1272 * <0 on error.
1273 */
1274 int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
1275 struct btrfs_key *key, struct btrfs_extent_item *ei,
1276 u32 item_size, u64 *out_root, u8 *out_level)
1277 {
1278 int ret;
1279 int type;
1280 struct btrfs_tree_block_info *info;
1281 struct btrfs_extent_inline_ref *eiref;
1282
1283 if (*ptr == (unsigned long)-1)
1284 return 1;
1285
1286 while (1) {
1287 ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size,
1288 &eiref, &type);
1289 if (ret < 0)
1290 return ret;
1291
1292 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1293 type == BTRFS_SHARED_BLOCK_REF_KEY)
1294 break;
1295
1296 if (ret == 1)
1297 return 1;
1298 }
1299
1300 /* we can treat both ref types equally here */
1301 info = (struct btrfs_tree_block_info *)(ei + 1);
1302 *out_root = btrfs_extent_inline_ref_offset(eb, eiref);
1303 *out_level = btrfs_tree_block_level(eb, info);
1304
1305 if (ret == 1)
1306 *ptr = (unsigned long)-1;
1307
1308 return 0;
1309 }
1310
1311 static int iterate_leaf_refs(struct extent_inode_elem *inode_list,
1312 u64 root, u64 extent_item_objectid,
1313 iterate_extent_inodes_t *iterate, void *ctx)
1314 {
1315 struct extent_inode_elem *eie;
1316 int ret = 0;
1317
1318 for (eie = inode_list; eie; eie = eie->next) {
1319 pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
1320 "root %llu\n", extent_item_objectid,
1321 eie->inum, eie->offset, root);
1322 ret = iterate(eie->inum, eie->offset, root, ctx);
1323 if (ret) {
1324 pr_debug("stopping iteration for %llu due to ret=%d\n",
1325 extent_item_objectid, ret);
1326 break;
1327 }
1328 }
1329
1330 return ret;
1331 }
1332
1333 /*
1334 * calls iterate() for every inode that references the extent identified by
1335 * the given parameters.
1336 * when the iterator function returns a non-zero value, iteration stops.
1337 */
1338 int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
1339 u64 extent_item_objectid, u64 extent_item_pos,
1340 int search_commit_root,
1341 iterate_extent_inodes_t *iterate, void *ctx)
1342 {
1343 int ret;
1344 struct btrfs_trans_handle *trans = NULL;
1345 struct ulist *refs = NULL;
1346 struct ulist *roots = NULL;
1347 struct ulist_node *ref_node = NULL;
1348 struct ulist_node *root_node = NULL;
1349 struct ulist_iterator ref_uiter;
1350 struct ulist_iterator root_uiter;
1351
1352 pr_debug("resolving all inodes for extent %llu\n",
1353 extent_item_objectid);
1354
1355 ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1356 0, &refs, &extent_item_pos);
1357 if (ret)
1358 goto out;
1359
1360 ULIST_ITER_INIT(&ref_uiter);
1361 while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1362 ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
1363 0, &roots);
1364 if (ret)
1365 break;
1366 ULIST_ITER_INIT(&root_uiter);
1367 while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1368 pr_debug("root %llu references leaf %llu, data list "
1369 "%#llx\n", root_node->val, ref_node->val,
1370 ref_node->aux);
1371 ret = iterate_leaf_refs((struct extent_inode_elem *)
1372 (uintptr_t)ref_node->aux,
1373 root_node->val,
1374 extent_item_objectid,
1375 iterate, ctx);
1376 }
1377 ulist_free(roots);
1378 }
1379
1380 free_leaf_list(refs);
1381 out:
1382 return ret;
1383 }
1384
1385 int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
1386 struct btrfs_path *path,
1387 iterate_extent_inodes_t *iterate, void *ctx)
1388 {
1389 int ret;
1390 u64 extent_item_pos;
1391 u64 flags = 0;
1392 struct btrfs_key found_key;
1393 int search_commit_root = 0;
1394
1395 ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
1396 btrfs_release_path(path);
1397 if (ret < 0)
1398 return ret;
1399 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1400 return -EINVAL;
1401
1402 extent_item_pos = logical - found_key.objectid;
1403 ret = iterate_extent_inodes(fs_info, found_key.objectid,
1404 extent_item_pos, search_commit_root,
1405 iterate, ctx);
1406
1407 return ret;
1408 }
1409
1410 typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
1411 struct extent_buffer *eb, void *ctx);
1412
1413 static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
1414 struct btrfs_path *path,
1415 iterate_irefs_t *iterate, void *ctx)
1416 {
1417 int ret = 0;
1418 int slot;
1419 u32 cur;
1420 u32 len;
1421 u32 name_len;
1422 u64 parent = 0;
1423 int found = 0;
1424 struct extent_buffer *eb;
1425 struct btrfs_item *item;
1426 struct btrfs_inode_ref *iref;
1427 struct btrfs_key found_key;
1428
1429 while (!ret) {
1430 ret = inode_ref_info(inum, parent ? parent+1 : 0, fs_root, path,
1431 &found_key);
1432 if (ret < 0)
1433 break;
1434 if (ret) {
1435 ret = found ? 0 : -ENOENT;
1436 break;
1437 }
1438 ++found;
1439
1440 parent = found_key.offset;
1441 slot = path->slots[0];
1442 eb = btrfs_clone_extent_buffer(path->nodes[0]);
1443 if (!eb) {
1444 ret = -ENOMEM;
1445 break;
1446 }
1447 extent_buffer_get(eb);
1448 btrfs_release_path(path);
1449
1450 item = btrfs_item_nr(slot);
1451 iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1452
1453 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
1454 name_len = btrfs_inode_ref_name_len(eb, iref);
1455 /* path must be released before calling iterate()! */
1456 pr_debug("following ref at offset %u for inode %llu in "
1457 "tree %llu\n", cur, found_key.objectid,
1458 fs_root->objectid);
1459 ret = iterate(parent, name_len,
1460 (unsigned long)(iref + 1), eb, ctx);
1461 if (ret)
1462 break;
1463 len = sizeof(*iref) + name_len;
1464 iref = (struct btrfs_inode_ref *)((char *)iref + len);
1465 }
1466 free_extent_buffer(eb);
1467 }
1468
1469 btrfs_release_path(path);
1470
1471 return ret;
1472 }
1473
1474 static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
1475 struct btrfs_path *path,
1476 iterate_irefs_t *iterate, void *ctx)
1477 {
1478 int ret;
1479 int slot;
1480 u64 offset = 0;
1481 u64 parent;
1482 int found = 0;
1483 struct extent_buffer *eb;
1484 struct btrfs_inode_extref *extref;
1485 struct extent_buffer *leaf;
1486 u32 item_size;
1487 u32 cur_offset;
1488 unsigned long ptr;
1489
1490 while (1) {
1491 ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
1492 &offset);
1493 if (ret < 0)
1494 break;
1495 if (ret) {
1496 ret = found ? 0 : -ENOENT;
1497 break;
1498 }
1499 ++found;
1500
1501 slot = path->slots[0];
1502 eb = btrfs_clone_extent_buffer(path->nodes[0]);
1503 if (!eb) {
1504 ret = -ENOMEM;
1505 break;
1506 }
1507 extent_buffer_get(eb);
1508
1509 btrfs_release_path(path);
1510
1511 leaf = path->nodes[0];
1512 item_size = btrfs_item_size_nr(leaf, slot);
1513 ptr = btrfs_item_ptr_offset(leaf, slot);
1514 cur_offset = 0;
1515
1516 while (cur_offset < item_size) {
1517 u32 name_len;
1518
1519 extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
1520 parent = btrfs_inode_extref_parent(eb, extref);
1521 name_len = btrfs_inode_extref_name_len(eb, extref);
1522 ret = iterate(parent, name_len,
1523 (unsigned long)&extref->name, eb, ctx);
1524 if (ret)
1525 break;
1526
1527 cur_offset += btrfs_inode_extref_name_len(leaf, extref);
1528 cur_offset += sizeof(*extref);
1529 }
1530 free_extent_buffer(eb);
1531
1532 offset++;
1533 }
1534
1535 btrfs_release_path(path);
1536
1537 return ret;
1538 }
1539
1540 static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
1541 struct btrfs_path *path, iterate_irefs_t *iterate,
1542 void *ctx)
1543 {
1544 int ret;
1545 int found_refs = 0;
1546
1547 ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
1548 if (!ret)
1549 ++found_refs;
1550 else if (ret != -ENOENT)
1551 return ret;
1552
1553 ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
1554 if (ret == -ENOENT && found_refs)
1555 return 0;
1556
1557 return ret;
1558 }
1559
1560 /*
1561 * returns 0 if the path could be dumped (probably truncated)
1562 * returns <0 in case of an error
1563 */
1564 static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
1565 struct extent_buffer *eb, void *ctx)
1566 {
1567 struct inode_fs_paths *ipath = ctx;
1568 char *fspath;
1569 char *fspath_min;
1570 int i = ipath->fspath->elem_cnt;
1571 const int s_ptr = sizeof(char *);
1572 u32 bytes_left;
1573
1574 bytes_left = ipath->fspath->bytes_left > s_ptr ?
1575 ipath->fspath->bytes_left - s_ptr : 0;
1576
1577 fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
1578 fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
1579 name_off, eb, inum, fspath_min, bytes_left);
1580 if (IS_ERR(fspath))
1581 return PTR_ERR(fspath);
1582
1583 if (fspath > fspath_min) {
1584 ipath->fspath->val[i] = (u64)(unsigned long)fspath;
1585 ++ipath->fspath->elem_cnt;
1586 ipath->fspath->bytes_left = fspath - fspath_min;
1587 } else {
1588 ++ipath->fspath->elem_missed;
1589 ipath->fspath->bytes_missing += fspath_min - fspath;
1590 ipath->fspath->bytes_left = 0;
1591 }
1592
1593 return 0;
1594 }
1595
1596 /*
1597 * this dumps all file system paths to the inode into the ipath struct, provided
1598 * is has been created large enough. each path is zero-terminated and accessed
1599 * from ipath->fspath->val[i].
1600 * when it returns, there are ipath->fspath->elem_cnt number of paths available
1601 * in ipath->fspath->val[]. When the allocated space wasn't sufficient, the
1602 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise,
1603 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
1604 * have been needed to return all paths.
1605 */
1606 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
1607 {
1608 return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
1609 inode_to_path, ipath);
1610 }
1611
1612 struct btrfs_data_container *init_data_container(u32 total_bytes)
1613 {
1614 struct btrfs_data_container *data;
1615 size_t alloc_bytes;
1616
1617 alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
1618 data = vmalloc(alloc_bytes);
1619 if (!data)
1620 return ERR_PTR(-ENOMEM);
1621
1622 if (total_bytes >= sizeof(*data)) {
1623 data->bytes_left = total_bytes - sizeof(*data);
1624 data->bytes_missing = 0;
1625 } else {
1626 data->bytes_missing = sizeof(*data) - total_bytes;
1627 data->bytes_left = 0;
1628 }
1629
1630 data->elem_cnt = 0;
1631 data->elem_missed = 0;
1632
1633 return data;
1634 }
1635
1636 /*
1637 * allocates space to return multiple file system paths for an inode.
1638 * total_bytes to allocate are passed, note that space usable for actual path
1639 * information will be total_bytes - sizeof(struct inode_fs_paths).
1640 * the returned pointer must be freed with free_ipath() in the end.
1641 */
1642 struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
1643 struct btrfs_path *path)
1644 {
1645 struct inode_fs_paths *ifp;
1646 struct btrfs_data_container *fspath;
1647
1648 fspath = init_data_container(total_bytes);
1649 if (IS_ERR(fspath))
1650 return (void *)fspath;
1651
1652 ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
1653 if (!ifp) {
1654 kfree(fspath);
1655 return ERR_PTR(-ENOMEM);
1656 }
1657
1658 ifp->btrfs_path = path;
1659 ifp->fspath = fspath;
1660 ifp->fs_root = fs_root;
1661
1662 return ifp;
1663 }
1664
1665 void free_ipath(struct inode_fs_paths *ipath)
1666 {
1667 if (!ipath)
1668 return;
1669 vfree(ipath->fspath);
1670 kfree(ipath);
1671 }
(deprecated) Btrfs progs developments and patch integration