~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/backref.c

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp