1 files changed, 98 insertions, 48 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index d7a96cfdc50a..8206b3900587 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -467,6 +467,15 @@ static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
         return 0;
 }
 
+/*
+ * This allocates memory and gets a tree modification sequence number when
+ * needed.
+ *
+ * Returns 0 when no sequence number is needed, < 0 on error.
+ * Returns 1 when a sequence number was added. In this case,
+ * fs_info->tree_mod_seq_lock was acquired and must be released by the caller
+ * after inserting into the rb tree.
+ */
 static inline int tree_mod_alloc(struct btrfs_fs_info *fs_info, gfp_t flags,
                                  struct tree_mod_elem **tm_ret)
 {
@@ -491,11 +500,11 @@ static inline int tree_mod_alloc(struct btrfs_fs_info *fs_info, gfp_t flags,
                  */
                 kfree(tm);
                 seq = 0;
+                spin_unlock(&fs_info->tree_mod_seq_lock);
         } else {
                 __get_tree_mod_seq(fs_info, &tm->elem);
                 seq = tm->elem.seq;
         }
-        spin_unlock(&fs_info->tree_mod_seq_lock);
 
         return seq;
 }
@@ -521,7 +530,9 @@ tree_mod_log_insert_key_mask(struct btrfs_fs_info *fs_info,
         tm->slot = slot;
         tm->generation = btrfs_node_ptr_generation(eb, slot);
 
-        return __tree_mod_log_insert(fs_info, tm);
+        ret = __tree_mod_log_insert(fs_info, tm);
+        spin_unlock(&fs_info->tree_mod_seq_lock);
+        return ret;
 }
 
 static noinline int
@@ -559,7 +570,9 @@ tree_mod_log_insert_move(struct btrfs_fs_info *fs_info,
         tm->move.nr_items = nr_items;
         tm->op = MOD_LOG_MOVE_KEYS;
 
-        return __tree_mod_log_insert(fs_info, tm);
+        ret = __tree_mod_log_insert(fs_info, tm);
+        spin_unlock(&fs_info->tree_mod_seq_lock);
+        return ret;
 }
 
 static noinline int
@@ -580,7 +593,9 @@ tree_mod_log_insert_root(struct btrfs_fs_info *fs_info,
         tm->generation = btrfs_header_generation(old_root);
         tm->op = MOD_LOG_ROOT_REPLACE;
 
-        return __tree_mod_log_insert(fs_info, tm);
+        ret = __tree_mod_log_insert(fs_info, tm);
+        spin_unlock(&fs_info->tree_mod_seq_lock);
+        return ret;
 }
 
 static struct tree_mod_elem *
@@ -1009,11 +1024,18 @@ __tree_mod_log_oldest_root(struct btrfs_fs_info *fs_info,
                 if (!looped && !tm)
                         return 0;
                 /*
-                 * we must have key remove operations in the log before the
-                 * replace operation.
+                 * if there are no tree operation for the oldest root, we simply
+                 * return it. this should only happen if that (old) root is at
+                 * level 0.
                  */
-                BUG_ON(!tm);
+                if (!tm)
+                        break;
 
+                /*
+                 * if there's an operation that's not a root replacement, we
+                 * found the oldest version of our root. normally, we'll find a
+                 * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
+                 */
                 if (tm->op != MOD_LOG_ROOT_REPLACE)
                         break;
 
@@ -1023,6 +1045,10 @@ __tree_mod_log_oldest_root(struct btrfs_fs_info *fs_info,
                 looped = 1;
         }
 
+        /* if there's no old root to return, return what we found instead */
+        if (!found)
+                found = tm;
+
         return found;
 }
 
@@ -1068,11 +1094,7 @@ __tree_mod_log_rewind(struct extent_buffer *eb, u64 time_seq,
                                                       tm->generation);
                         break;
                 case MOD_LOG_KEY_ADD:
-                        if (tm->slot != n - 1) {
-                                o_dst = btrfs_node_key_ptr_offset(tm->slot);
-                                o_src = btrfs_node_key_ptr_offset(tm->slot + 1);
-                                memmove_extent_buffer(eb, o_dst, o_src, p_size);
-                        }
+                        /* if a move operation is needed it's in the log */
                         n--;
                         break;
                 case MOD_LOG_MOVE_KEYS:
@@ -1143,45 +1165,57 @@ tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
         return eb_rewin;
 }
 
+/*
+ * get_old_root() rewinds the state of @root's root node to the given @time_seq
+ * value. If there are no changes, the current root->root_node is returned. If
+ * anything changed in between, there's a fresh buffer allocated on which the
+ * rewind operations are done. In any case, the returned buffer is read locked.
+ * Returns NULL on error (with no locks held).
+ */
 static inline struct extent_buffer *
 get_old_root(struct btrfs_root *root, u64 time_seq)
 {
         struct tree_mod_elem *tm;
         struct extent_buffer *eb;
-        struct tree_mod_root *old_root;
-        u64 old_generation;
+        struct tree_mod_root *old_root = NULL;
+        u64 old_generation = 0;
+        u64 logical;
 
+        eb = btrfs_read_lock_root_node(root);
         tm = __tree_mod_log_oldest_root(root->fs_info, root, time_seq);
         if (!tm)
                 return root->node;
 
-        old_root = &tm->old_root;
-        old_generation = tm->generation;
-
-        tm = tree_mod_log_search(root->fs_info, old_root->logical, time_seq);
-        /*
-         * there was an item in the log when __tree_mod_log_oldest_root
-         * returned. this one must not go away, because the time_seq passed to
-         * us must be blocking its removal.
-         */
-        BUG_ON(!tm);
+        if (tm->op == MOD_LOG_ROOT_REPLACE) {
+                old_root = &tm->old_root;
+                old_generation = tm->generation;
+                logical = old_root->logical;
+        } else {
+                logical = root->node->start;
+        }
 
-        if (old_root->logical == root->node->start) {
-                /* there are logged operations for the current root */
+        tm = tree_mod_log_search(root->fs_info, logical, time_seq);
+        if (old_root)
+                eb = alloc_dummy_extent_buffer(logical, root->nodesize);
+        else
                 eb = btrfs_clone_extent_buffer(root->node);
-        } else {
-                /* there's a root replace operation for the current root */
-                eb = alloc_dummy_extent_buffer(tm->index << PAGE_CACHE_SHIFT,
-                                               root->nodesize);
+        btrfs_tree_read_unlock(root->node);
+        free_extent_buffer(root->node);
+        if (!eb)
+                return NULL;
+        btrfs_tree_read_lock(eb);
+        if (old_root) {
                 btrfs_set_header_bytenr(eb, eb->start);
                 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
                 btrfs_set_header_owner(eb, root->root_key.objectid);
+                btrfs_set_header_level(eb, old_root->level);
+                btrfs_set_header_generation(eb, old_generation);
         }
-        if (!eb)
-                return NULL;
-        btrfs_set_header_level(eb, old_root->level);
-        btrfs_set_header_generation(eb, old_generation);
-        __tree_mod_log_rewind(eb, time_seq, tm);
+        if (tm)
+                __tree_mod_log_rewind(eb, time_seq, tm);
+        else
+                WARN_ON(btrfs_header_level(eb) != 0);
+        extent_buffer_get(eb);
 
         return eb;
 }
@@ -1650,8 +1684,6 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
                 return 0;
 
-        btrfs_header_nritems(mid);
-
         left = read_node_slot(root, parent, pslot - 1);
         if (left) {
                 btrfs_tree_lock(left);
@@ -1681,7 +1713,6 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
                 wret = push_node_left(trans, root, left, mid, 1);
                 if (wret < 0)
                         ret = wret;
-                btrfs_header_nritems(mid);
         }
 
         /*
@@ -2615,9 +2646,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
 
 again:
         b = get_old_root(root, time_seq);
-        extent_buffer_get(b);
         level = btrfs_header_level(b);
-        btrfs_tree_read_lock(b);
         p->locks[level] = BTRFS_READ_LOCK;
 
         while (b) {
@@ -2964,7 +2993,7 @@ static noinline int insert_new_root(struct btrfs_trans_handle *trans,
 static void insert_ptr(struct btrfs_trans_handle *trans,
                        struct btrfs_root *root, struct btrfs_path *path,
                        struct btrfs_disk_key *key, u64 bytenr,
-                       int slot, int level, int tree_mod_log)
+                       int slot, int level)
 {
         struct extent_buffer *lower;
         int nritems;
@@ -2977,7 +3006,7 @@ static void insert_ptr(struct btrfs_trans_handle *trans,
         BUG_ON(slot > nritems);
         BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(root));
         if (slot != nritems) {
-                if (tree_mod_log && level)
+                if (level)
                         tree_mod_log_eb_move(root->fs_info, lower, slot + 1,
                                              slot, nritems - slot);
                 memmove_extent_buffer(lower,
@@ -2985,7 +3014,7 @@ static void insert_ptr(struct btrfs_trans_handle *trans,
                               btrfs_node_key_ptr_offset(slot),
                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
         }
-        if (tree_mod_log && level) {
+        if (level) {
                 ret = tree_mod_log_insert_key(root->fs_info, lower, slot,
                                               MOD_LOG_KEY_ADD);
                 BUG_ON(ret < 0);
@@ -3073,7 +3102,7 @@ static noinline int split_node(struct btrfs_trans_handle *trans,
         btrfs_mark_buffer_dirty(split);
 
         insert_ptr(trans, root, path, &disk_key, split->start,
-                   path->slots[level + 1] + 1, level + 1, 1);
+                   path->slots[level + 1] + 1, level + 1);
 
         if (path->slots[level] >= mid) {
                 path->slots[level] -= mid;
@@ -3610,7 +3639,7 @@ static noinline void copy_for_split(struct btrfs_trans_handle *trans,
         btrfs_set_header_nritems(l, mid);
         btrfs_item_key(right, &disk_key, 0);
         insert_ptr(trans, root, path, &disk_key, right->start,
-                   path->slots[1] + 1, 1, 0);
+                   path->slots[1] + 1, 1);
 
         btrfs_mark_buffer_dirty(right);
         btrfs_mark_buffer_dirty(l);
@@ -3817,7 +3846,7 @@ again:
                 if (mid <= slot) {
                         btrfs_set_header_nritems(right, 0);
                         insert_ptr(trans, root, path, &disk_key, right->start,
-                                   path->slots[1] + 1, 1, 0);
+                                   path->slots[1] + 1, 1);
                         btrfs_tree_unlock(path->nodes[0]);
                         free_extent_buffer(path->nodes[0]);
                         path->nodes[0] = right;
@@ -3826,7 +3855,7 @@ again:
                 } else {
                         btrfs_set_header_nritems(right, 0);
                         insert_ptr(trans, root, path, &disk_key, right->start,
-                                          path->slots[1], 1, 0);
+                                          path->slots[1], 1);
                         btrfs_tree_unlock(path->nodes[0]);
                         free_extent_buffer(path->nodes[0]);
                         path->nodes[0] = right;
@@ -5001,6 +5030,12 @@ next:
  */
 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
 {
+        return btrfs_next_old_leaf(root, path, 0);
+}
+
+int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
+                        u64 time_seq)
+{
         int slot;
         int level;
         struct extent_buffer *c;
@@ -5025,7 +5060,10 @@ again:
         path->keep_locks = 1;
         path->leave_spinning = 1;
 
-        ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+        if (time_seq)
+                ret = btrfs_search_old_slot(root, &key, path, time_seq);
+        else
+                ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
         path->keep_locks = 0;
 
         if (ret < 0)
@@ -5081,6 +5119,18 @@ again:
 
                 if (!path->skip_locking) {
                         ret = btrfs_try_tree_read_lock(next);
+                        if (!ret && time_seq) {
+                                /*
+                                 * If we don't get the lock, we may be racing
+                                 * with push_leaf_left, holding that lock while
+                                 * itself waiting for the leaf we've currently
+                                 * locked. To solve this situation, we give up
+                                 * on our lock and cycle.
+                                 */
+                                btrfs_release_path(path);
+                                cond_resched();
+                                goto again;
+                        }
                         if (!ret) {
                                 btrfs_set_path_blocking(path);
                                 btrfs_tree_read_lock(next);