3 files changed, 107 insertions, 262 deletions

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 03c30a1836f4..b9a843226de8 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -23,18 +23,6 @@
 #include "transaction.h"
 #include "delayed-ref.h"
 
-struct __data_ref {
-        struct list_head list;
-        u64 inum;
-        u64 root;
-        u64 extent_data_item_offset;
-};
-
-struct __shared_ref {
-        struct list_head list;
-        u64 disk_byte;
-};
-
 /*
  * this structure records all encountered refs on the way up to the root
  */
@@ -964,8 +952,11 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
         btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
         if (found_key->type != BTRFS_EXTENT_ITEM_KEY ||
             found_key->objectid > logical ||
-            found_key->objectid + found_key->offset <= logical)
+            found_key->objectid + found_key->offset <= logical) {
+                pr_debug("logical %llu is not within any extent\n",
+                         (unsigned long long)logical);
                 return -ENOENT;
+        }
 
         eb = path->nodes[0];
         item_size = btrfs_item_size_nr(eb, path->slots[0]);
@@ -974,6 +965,13 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
         ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
         flags = btrfs_extent_flags(eb, ei);
 
+        pr_debug("logical %llu is at position %llu within the extent (%llu "
+                 "EXTENT_ITEM %llu) flags %#llx size %u\n",
+                 (unsigned long long)logical,
+                 (unsigned long long)(logical - found_key->objectid),
+                 (unsigned long long)found_key->objectid,
+                 (unsigned long long)found_key->offset,
+                 (unsigned long long)flags, item_size);
         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
                 return BTRFS_EXTENT_FLAG_TREE_BLOCK;
         if (flags & BTRFS_EXTENT_FLAG_DATA)
@@ -1070,128 +1068,11 @@ int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
         return 0;
 }
 
-static int __data_list_add(struct list_head *head, u64 inum,
-                                u64 extent_data_item_offset, u64 root)
-{
-        struct __data_ref *ref;
-
-        ref = kmalloc(sizeof(*ref), GFP_NOFS);
-        if (!ref)
-                return -ENOMEM;
-
-        ref->inum = inum;
-        ref->extent_data_item_offset = extent_data_item_offset;
-        ref->root = root;
-        list_add_tail(&ref->list, head);
-
-        return 0;
-}
-
-static int __data_list_add_eb(struct list_head *head, struct extent_buffer *eb,
-                                struct btrfs_extent_data_ref *dref)
-{
-        return __data_list_add(head, btrfs_extent_data_ref_objectid(eb, dref),
-                                btrfs_extent_data_ref_offset(eb, dref),
-                                btrfs_extent_data_ref_root(eb, dref));
-}
-
-static int __shared_list_add(struct list_head *head, u64 disk_byte)
-{
-        struct __shared_ref *ref;
-
-        ref = kmalloc(sizeof(*ref), GFP_NOFS);
-        if (!ref)
-                return -ENOMEM;
-
-        ref->disk_byte = disk_byte;
-        list_add_tail(&ref->list, head);
-
-        return 0;
-}
-
-static int __iter_shared_inline_ref_inodes(struct btrfs_fs_info *fs_info,
-                                           u64 logical, u64 inum,
-                                           u64 extent_data_item_offset,
-                                           u64 extent_offset,
-                                           struct btrfs_path *path,
-                                           struct list_head *data_refs,
-                                           iterate_extent_inodes_t *iterate,
-                                           void *ctx)
-{
-        u64 ref_root;
-        u32 item_size;
-        struct btrfs_key key;
-        struct extent_buffer *eb;
-        struct btrfs_extent_item *ei;
-        struct btrfs_extent_inline_ref *eiref;
-        struct __data_ref *ref;
-        int ret;
-        int type;
-        int last;
-        unsigned long ptr = 0;
-
-        WARN_ON(!list_empty(data_refs));
-        ret = extent_from_logical(fs_info, logical, path, &key);
-        if (ret & BTRFS_EXTENT_FLAG_DATA)
-                ret = -EIO;
-        if (ret < 0)
-                goto out;
-
-        eb = path->nodes[0];
-        ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
-        item_size = btrfs_item_size_nr(eb, path->slots[0]);
-
-        ret = 0;
-        ref_root = 0;
-        /*
-         * as done in iterate_extent_inodes, we first build a list of refs to
-         * iterate, then free the path and then iterate them to avoid deadlocks.
-         */
-        do {
-                last = __get_extent_inline_ref(&ptr, eb, ei, item_size,
-                                                &eiref, &type);
-                if (last < 0) {
-                        ret = last;
-                        goto out;
-                }
-                if (type == BTRFS_TREE_BLOCK_REF_KEY ||
-                    type == BTRFS_SHARED_BLOCK_REF_KEY) {
-                        ref_root = btrfs_extent_inline_ref_offset(eb, eiref);
-                        ret = __data_list_add(data_refs, inum,
-                                                extent_data_item_offset,
-                                                ref_root);
-                }
-        } while (!ret && !last);
-
-        btrfs_release_path(path);
-
-        if (ref_root == 0) {
-                printk(KERN_ERR "btrfs: failed to find tree block ref "
-                        "for shared data backref %llu\n", logical);
-                WARN_ON(1);
-                ret = -EIO;
-        }
-
-out:
-        while (!list_empty(data_refs)) {
-                ref = list_first_entry(data_refs, struct __data_ref, list);
-                list_del(&ref->list);
-                if (!ret)
-                        ret = iterate(ref->inum, extent_offset +
-                                        ref->extent_data_item_offset,
-                                        ref->root, ctx);
-                kfree(ref);
-        }
-
-        return ret;
-}
-
-static int __iter_shared_inline_ref(struct btrfs_fs_info *fs_info,
-                                    u64 logical, u64 orig_extent_item_objectid,
-                                    u64 extent_offset, struct btrfs_path *path,
-                                    struct list_head *data_refs,
-                                    iterate_extent_inodes_t *iterate,
-                                    void *ctx)
+static int iterate_leaf_refs(struct btrfs_fs_info *fs_info,
+                                struct btrfs_path *path, u64 logical,
+                                u64 orig_extent_item_objectid,
+                                u64 extent_item_pos, u64 root,
+                                iterate_extent_inodes_t *iterate, void *ctx)
 {
         u64 disk_byte;
         struct btrfs_key key;
@@ -1199,8 +1080,10 @@ static int __iter_shared_inline_ref(struct btrfs_fs_info *fs_info,
         struct extent_buffer *eb;
         int slot;
         int nritems;
-        int ret;
-        int found = 0;
+        int ret = 0;
+        int extent_type;
+        u64 data_offset;
+        u64 data_len;
 
         eb = read_tree_block(fs_info->tree_root, logical,
                                 fs_info->tree_root->leafsize, 0);
@@ -1218,149 +1101,99 @@ static int __iter_shared_inline_ref(struct btrfs_fs_info *fs_info,
                 if (key.type != BTRFS_EXTENT_DATA_KEY)
                         continue;
                 fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
-                if (!fi) {
-                        free_extent_buffer(eb);
-                        return -EIO;
-                }
+                extent_type = btrfs_file_extent_type(eb, fi);
+                if (extent_type == BTRFS_FILE_EXTENT_INLINE)
+                        continue;
+                /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
                 disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
-                if (disk_byte != orig_extent_item_objectid) {
-                        if (found)
-                                break;
-                        else
-                                continue;
-                }
-                ++found;
-                ret = __iter_shared_inline_ref_inodes(fs_info, logical,
-                                                        key.objectid,
-                                                        key.offset,
-                                                        extent_offset, path,
-                                                        data_refs,
-                                                        iterate, ctx);
-                if (ret)
-                        break;
-        }
+                if (disk_byte != orig_extent_item_objectid)
+                        continue;
 
-        if (!found) {
-                printk(KERN_ERR "btrfs: failed to follow shared data backref "
-                        "to parent %llu\n", logical);
-                WARN_ON(1);
-                ret = -EIO;
+                data_offset = btrfs_file_extent_offset(eb, fi);
+                data_len = btrfs_file_extent_num_bytes(eb, fi);
+
+                if (extent_item_pos < data_offset ||
+                    extent_item_pos >= data_offset + data_len)
+                        continue;
+
+                pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
+                                "root %llu\n", orig_extent_item_objectid,
+                                key.objectid, key.offset, root);
+                ret = iterate(key.objectid,
+                                key.offset + (extent_item_pos - data_offset),
+                                root, ctx);
+                if (ret) {
+                        pr_debug("stopping iteration because ret=%d\n", ret);
+                        break;
+                }
         }
 
         free_extent_buffer(eb);
+
         return ret;
 }
 
 /*
  * calls iterate() for every inode that references the extent identified by
- * the given parameters. will use the path given as a parameter and return it
- * released.
+ * the given parameters.
  * when the iterator function returns a non-zero value, iteration stops.
+ * path is guaranteed to be in released state when iterate() is called.
  */
 int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
                                 struct btrfs_path *path,
-                                u64 extent_item_objectid,
-                                u64 extent_offset,
+                                u64 extent_item_objectid, u64 extent_item_pos,
                                 iterate_extent_inodes_t *iterate, void *ctx)
 {
-        unsigned long ptr = 0;
-        int last;
         int ret;
-        int type;
-        u64 logical;
-        u32 item_size;
-        struct btrfs_extent_inline_ref *eiref;
-        struct btrfs_extent_data_ref *dref;
-        struct extent_buffer *eb;
-        struct btrfs_extent_item *ei;
-        struct btrfs_key key;
         struct list_head data_refs = LIST_HEAD_INIT(data_refs);
         struct list_head shared_refs = LIST_HEAD_INIT(shared_refs);
-        struct __data_ref *ref_d;
-        struct __shared_ref *ref_s;
+        struct btrfs_trans_handle *trans;
+        struct ulist *refs;
+        struct ulist *roots;
+        struct ulist_node *ref_node = NULL;
+        struct ulist_node *root_node = NULL;
+        struct seq_list seq_elem;
+        struct btrfs_delayed_ref_root *delayed_refs;
 
-        eb = path->nodes[0];
-        ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
-        item_size = btrfs_item_size_nr(eb, path->slots[0]);
-
-        /* first we iterate the inline refs, ... */
-        do {
-                last = __get_extent_inline_ref(&ptr, eb, ei, item_size,
-                                                &eiref, &type);
-                if (last == -ENOENT) {
-                        ret = 0;
-                        break;
-                }
-                if (last < 0) {
-                        ret = last;
-                        break;
-                }
+        trans = btrfs_join_transaction(fs_info->extent_root);
+        if (IS_ERR(trans))
+                return PTR_ERR(trans);
 
-                if (type == BTRFS_EXTENT_DATA_REF_KEY) {
-                        dref = (struct btrfs_extent_data_ref *)(&eiref->offset);
-                        ret = __data_list_add_eb(&data_refs, eb, dref);
-                } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
-                        logical = btrfs_extent_inline_ref_offset(eb, eiref);
-                        ret = __shared_list_add(&shared_refs, logical);
-                }
-        } while (!ret && !last);
+        pr_debug("resolving all inodes for extent %llu\n",
+                        extent_item_objectid);
 
-        /* ... then we proceed to in-tree references and ... */
-        while (!ret) {
-                ++path->slots[0];
-                if (path->slots[0] > btrfs_header_nritems(eb)) {
-                        ret = btrfs_next_leaf(fs_info->extent_root, path);
-                        if (ret) {
-                                if (ret == 1)
-                                        ret = 0; /* we're done */
-                                break;
-                        }
-                        eb = path->nodes[0];
-                }
-                btrfs_item_key_to_cpu(eb, &key, path->slots[0]);
-                if (key.objectid != extent_item_objectid)
-                        break;
-                if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
-                        dref = btrfs_item_ptr(eb, path->slots[0],
-                                                struct btrfs_extent_data_ref);
-                        ret = __data_list_add_eb(&data_refs, eb, dref);
-                } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
-                        ret = __shared_list_add(&shared_refs, key.offset);
-                }
-        }
+        delayed_refs = &trans->transaction->delayed_refs;
+        spin_lock(&delayed_refs->lock);
+        btrfs_get_delayed_seq(delayed_refs, &seq_elem);
+        spin_unlock(&delayed_refs->lock);
 
-        btrfs_release_path(path);
+        ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
+                                   extent_item_pos, seq_elem.seq,
+                                   &refs);
 
-        /*
-         * ... only at the very end we can process the refs we found. this is
-         * because the iterator function we call is allowed to make tree lookups
-         * and we have to avoid deadlocks. additionally, we need more tree
-         * lookups ourselves for shared data refs.
-         */
-        while (!list_empty(&data_refs)) {
-                ref_d = list_first_entry(&data_refs, struct __data_ref, list);
-                list_del(&ref_d->list);
-                if (!ret)
-                        ret = iterate(ref_d->inum, extent_offset +
-                                        ref_d->extent_data_item_offset,
-                                        ref_d->root, ctx);
-                kfree(ref_d);
-        }
+        if (ret)
+                goto out;
 
-        while (!list_empty(&shared_refs)) {
-                ref_s = list_first_entry(&shared_refs, struct __shared_ref,
-                                        list);
-                list_del(&ref_s->list);
-                if (!ret)
-                        ret = __iter_shared_inline_ref(fs_info,
-                                                        ref_s->disk_byte,
-                                                        extent_item_objectid,
-                                                        extent_offset, path,
-                                                        &data_refs,
-                                                        iterate, ctx);
-                kfree(ref_s);
+        while (!ret && (ref_node = ulist_next(refs, ref_node))) {
+                ret = btrfs_find_all_roots(trans, fs_info, ref_node->val, -1,
+                                                seq_elem.seq, &roots);
+                if (ret)
+                        break;
+                while (!ret && (root_node = ulist_next(roots, root_node))) {
+                        pr_debug("root %llu references leaf %llu\n",
+                                        root_node->val, ref_node->val);
+                        ret = iterate_leaf_refs(fs_info, path, ref_node->val,
+                                                extent_item_objectid,
+                                                extent_item_pos, root_node->val,
+                                                iterate, ctx);
+                }
         }
 
+        ulist_free(refs);
+        ulist_free(roots);
+out:
+        btrfs_put_delayed_seq(delayed_refs, &seq_elem);
+        btrfs_end_transaction(trans, fs_info->extent_root);
         return ret;
 }
 
@@ -1369,19 +1202,20 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
                                 iterate_extent_inodes_t *iterate, void *ctx)
 {
         int ret;
-        u64 offset;
+        u64 extent_item_pos;
         struct btrfs_key found_key;
 
         ret = extent_from_logical(fs_info, logical, path,
                                         &found_key);
+        btrfs_release_path(path);
         if (ret & BTRFS_EXTENT_FLAG_TREE_BLOCK)
                 ret = -EINVAL;
         if (ret < 0)
                 return ret;
 
-        offset = logical - found_key.objectid;
+        extent_item_pos = logical - found_key.objectid;
         ret = iterate_extent_inodes(fs_info, path, found_key.objectid,
-                                        offset, iterate, ctx);
+                                        extent_item_pos, iterate, ctx);
 
         return ret;
 }
@@ -1426,6 +1260,10 @@ static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
                 for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
                         name_len = btrfs_inode_ref_name_len(eb, iref);
                         /* path must be released before calling iterate()! */
+                        pr_debug("following ref at offset %u for inode %llu in "
+                                 "tree %llu\n", cur,
+                                 (unsigned long long)found_key.objectid,
+                                 (unsigned long long)fs_root->objectid);
                         ret = iterate(parent, iref, eb, ctx);
                         if (ret) {
                                 free_extent_buffer(eb);
@@ -1466,10 +1304,14 @@ static int inode_to_path(u64 inum, struct btrfs_inode_ref *iref,
                 return PTR_ERR(fspath);
 
         if (fspath > fspath_min) {
+                pr_debug("path resolved: %s\n", fspath);
                 ipath->fspath->val[i] = (u64)(unsigned long)fspath;
                 ++ipath->fspath->elem_cnt;
                 ipath->fspath->bytes_left = fspath - fspath_min;
         } else {
+                pr_debug("missed path, not enough space. missing bytes: %lu, "
+                         "constructed so far: %s\n",
+                         (unsigned long)(fspath_min - fspath), fspath_min);
                 ++ipath->fspath->elem_missed;
                 ipath->fspath->bytes_missing += fspath_min - fspath;
                 ipath->fspath->bytes_left = 0;
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index c48f2e931ea0..9b0526872b7b 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -2976,7 +2976,7 @@ static long btrfs_ioctl_logical_to_ino(struct btrfs_root *root,
 {
         int ret = 0;
         int size;
-        u64 extent_offset;
+        u64 extent_item_pos;
         struct btrfs_ioctl_logical_ino_args *loi;
         struct btrfs_data_container *inodes = NULL;
         struct btrfs_path *path = NULL;
@@ -3007,15 +3007,17 @@ static long btrfs_ioctl_logical_to_ino(struct btrfs_root *root,
         }
 
         ret = extent_from_logical(root->fs_info, loi->logical, path, &key);
+        btrfs_release_path(path);
 
         if (ret & BTRFS_EXTENT_FLAG_TREE_BLOCK)
                 ret = -ENOENT;
         if (ret < 0)
                 goto out;
 
-        extent_offset = loi->logical - key.objectid;
+        extent_item_pos = loi->logical - key.objectid;
         ret = iterate_extent_inodes(root->fs_info, path, key.objectid,
-                                        extent_offset, build_ino_list, inodes);
+                                        extent_item_pos, build_ino_list,
+                                        inodes);
 
         if (ret < 0)
                 goto out;
diff --git a/fs/btrfs/scrub.c b/fs/btrfs/scrub.c
index c27bcb67f330..b5edff25a53f 100644
--- a/fs/btrfs/scrub.c
+++ b/fs/btrfs/scrub.c
@@ -309,7 +309,7 @@ static void scrub_print_warning(const char *errstr, struct scrub_bio *sbio,
         u8 ref_level;
         unsigned long ptr = 0;
         const int bufsize = 4096;
-        u64 extent_offset;
+        u64 extent_item_pos;
 
         path = btrfs_alloc_path();
 
@@ -329,12 +329,13 @@ static void scrub_print_warning(const char *errstr, struct scrub_bio *sbio,
         if (ret < 0)
                 goto out;
 
-        extent_offset = swarn.logical - found_key.objectid;
+        extent_item_pos = swarn.logical - found_key.objectid;
         swarn.extent_item_size = found_key.offset;
 
         eb = path->nodes[0];
         ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
         item_size = btrfs_item_size_nr(eb, path->slots[0]);
+        btrfs_release_path(path);
 
         if (ret & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
                 do {
@@ -351,7 +352,7 @@ static void scrub_print_warning(const char *errstr, struct scrub_bio *sbio,
         } else {
                 swarn.path = path;
                 iterate_extent_inodes(fs_info, path, found_key.objectid,
-                                        extent_offset,
+                                        extent_item_pos,
                                         scrub_print_warning_inode, &swarn);
         }