[PATCH 0/6] Btrfs: tree mod log fixes for 3.5-rc3

[PATCH 0/6] Btrfs: tree mod log fixes for 3.5-rc3

[Jan Schmidt]

Hi Chris,

This are my current fixes for the tree mod log. With these patches,
backref walking looks really stable now. My qgroup tests are getting
really close to succeeding :-)

Everything's pretty small and non-invasive, so it should be fine for the
upcomming rc.

You can also pull from

	git://git.jan-o-sch.net/btrfs-unstable for-chris

Thanks,
Jan

Jan Schmidt (6):
  Btrfs: remove call to btrfs_header_nritems with no effect
  Btrfs: remove obsolete btrfs_next_leaf call from
    __resolve_indirect_ref
  Btrfs: use btrfs_read_lock_root_node in get_old_root
  Btrfs: fix return value for __tree_mod_log_oldest_root
  Btrfs: add btrfs_next_old_leaf
  Btrfs: fix race in tree mod log addition

 fs/btrfs/backref.c |   17 +++-------
 fs/btrfs/ctree.c   |   86 ++++++++++++++++++++++++++++++++++++++--------------
 fs/btrfs/ctree.h   |    2 +
 3 files changed, 70 insertions(+), 35 deletions(-)

-- 
1.7.3.4

[PATCH 1/6] Btrfs: remove call to btrfs_header_nritems with no effect

[Jan Schmidt]

This is a leftover from cleanup patch 559af821. Before the cleanup,
btrfs_header_nritems was called inside an if condition. As it has no side
effects we need to preserve here, it should simply be dropped.

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/ctree.c |    3 ---
 1 files changed, 0 insertions(+), 3 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index d7a96cf..836e4e0 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -1650,8 +1650,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 +1679,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);
 	}
 
 	/*
-- 
1.7.3.4

[PATCH 2/6] Btrfs: remove obsolete btrfs_next_leaf call from __resolve_indirect_ref

[Jan Schmidt]

When resolving indirect refs, we used to call btrfs_next_leaf in case we
didn't find an exact match. While we should find exact matches most of the
time, in case we don't, we must continue searching. Treating those matches
differently depending on the level we're searching doesn't make sense.

Even worse, we might end up searching for a key larger than the largest, in
which case there is no next_leaf and subsequent jobs would fail. This commit
drops the bogous lines.

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/backref.c |   10 +---------
 1 files changed, 1 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 3f75895..579131d 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -294,16 +294,8 @@ static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
 		goto out;
 	}
 
-	if (level == 0) {
-		if (ret == 1 && path->slots[0] >= btrfs_header_nritems(eb)) {
-			ret = btrfs_next_leaf(root, path);
-			if (ret)
-				goto out;
-			eb = path->nodes[0];
-		}
-
+	if (level == 0)
 		btrfs_item_key_to_cpu(eb, &key, path->slots[0]);
-	}
 
 	ret = add_all_parents(root, path, parents, level, &key,
 				ref->wanted_disk_byte, extent_item_pos);
-- 
1.7.3.4

[PATCH 3/6] Btrfs: use btrfs_read_lock_root_node in get_old_root

[Jan Schmidt]

get_old_root could race with root node updates because we weren't locking
the node early enough. Use btrfs_read_lock_root_node to grab the root locked
in the very beginning and release the lock as soon as possible (just like
btrfs_search_slot does).

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/ctree.c |   20 ++++++++++++++++----
 1 files changed, 16 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 836e4e0..2cde7b0 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -1143,6 +1143,13 @@ 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)
 {
@@ -1151,6 +1158,7 @@ get_old_root(struct btrfs_root *root, u64 time_seq)
 	struct tree_mod_root *old_root;
 	u64 old_generation;
 
+	eb = btrfs_read_lock_root_node(root);
 	tm = __tree_mod_log_oldest_root(root->fs_info, root, time_seq);
 	if (!tm)
 		return root->node;
@@ -1173,15 +1181,21 @@ get_old_root(struct btrfs_root *root, u64 time_seq)
 		/* 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->logical != root->node->start) {
 		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);
 	}
-	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);
+	extent_buffer_get(eb);
 
 	return eb;
 }
@@ -2612,9 +2626,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) {
-- 
1.7.3.4

[PATCH 4/6] Btrfs: fix return value for __tree_mod_log_oldest_root

[Jan Schmidt]

In __tree_mod_log_oldest_root() we must return the found operation even if
it's not a ROOT_REPLACE operation. Otherwise, the caller assumes that there
are no operations to be rewinded and returns immediately.

The code in the caller is modified to improve readability.

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/ctree.c |   33 ++++++++++++++++++++-------------
 1 files changed, 20 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 2cde7b0..50d7c99 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -1023,6 +1023,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;
 }
 
@@ -1155,18 +1159,24 @@ 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;
+	struct tree_mod_root *old_root = NULL;
 	u64 old_generation;
+	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;
+	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;
+	}
 
-	tm = tree_mod_log_search(root->fs_info, old_root->logical, time_seq);
+	tm = tree_mod_log_search(root->fs_info, 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
@@ -1174,26 +1184,23 @@ get_old_root(struct btrfs_root *root, u64 time_seq)
 	 */
 	BUG_ON(!tm);
 
-	if (old_root->logical == root->node->start) {
-		/* there are logged operations for the current root */
-		eb = btrfs_clone_extent_buffer(root->node);
-	} else {
-		/* there's a root replace operation for the current root */
+	if (old_root)
 		eb = alloc_dummy_extent_buffer(tm->index << PAGE_CACHE_SHIFT,
 					       root->nodesize);
-	}
+	else
+		eb = btrfs_clone_extent_buffer(root->node);
 	btrfs_tree_read_unlock(root->node);
 	free_extent_buffer(root->node);
 	if (!eb)
 		return NULL;
 	btrfs_tree_read_lock(eb);
-	if (old_root->logical != root->node->start) {
+	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);
 	}
-	btrfs_set_header_level(eb, old_root->level);
-	btrfs_set_header_generation(eb, old_generation);
 	__tree_mod_log_rewind(eb, time_seq, tm);
 	extent_buffer_get(eb);
 
-- 
1.7.3.4

[PATCH 5/6] Btrfs: add btrfs_next_old_leaf

[Jan Schmidt]

To make sense of the tree mod log, the backref walker not only needs
btrfs_search_old_slot, but it also called btrfs_next_leaf, which in turn was
calling btrfs_search_slot. This obviously didn't give the correct result.

This commit adds btrfs_next_old_leaf, a drop-in replacement for
btrfs_next_leaf with a time_seq parameter. If it is zero, it behaves exactly
like btrfs_next_leaf. If it is non-zero, it will use btrfs_search_old_slot
with this time_seq parameter.

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/backref.c |    7 ++++---
 fs/btrfs/ctree.c   |   11 ++++++++++-
 fs/btrfs/ctree.h   |    2 ++
 3 files changed, 16 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 579131d..8f7d123 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -179,7 +179,8 @@ static int __add_prelim_ref(struct list_head *head, u64 root_id,
 
 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
 				struct ulist *parents, int level,
-				struct btrfs_key *key, u64 wanted_disk_byte,
+				struct btrfs_key *key, u64 time_seq,
+				u64 wanted_disk_byte,
 				const u64 *extent_item_pos)
 {
 	int ret;
@@ -212,7 +213,7 @@ add_parent:
 	 */
 	while (1) {
 		eie = NULL;
-		ret = btrfs_next_leaf(root, path);
+		ret = btrfs_next_old_leaf(root, path, time_seq);
 		if (ret < 0)
 			return ret;
 		if (ret)
@@ -297,7 +298,7 @@ static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
 	if (level == 0)
 		btrfs_item_key_to_cpu(eb, &key, path->slots[0]);
 
-	ret = add_all_parents(root, path, parents, level, &key,
+	ret = add_all_parents(root, path, parents, level, &key, time_seq,
 				ref->wanted_disk_byte, extent_item_pos);
 out:
 	btrfs_free_path(path);
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 50d7c99..cb76b2a 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -5017,6 +5017,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;
@@ -5041,7 +5047,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)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 0151ca1..db15e9e 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -2753,6 +2753,8 @@ static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
 }
 
 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
+int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
+			u64 time_seq);
 static inline int btrfs_next_item(struct btrfs_root *root, struct btrfs_path *p)
 {
 	++p->slots[0];
-- 
1.7.3.4

[PATCH 6/6] Btrfs: fix race in tree mod log addition

[Jan Schmidt]

When adding to the tree modification log, we grab two locks at different
stages. We must not drop the outer lock until we're done with section
protected by the inner lock. This moves the unlock call for the outer lock
to the appropriate position.

Signed-off-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
---
 fs/btrfs/ctree.c |   23 +++++++++++++++++++----
 1 files changed, 19 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index cb76b2a..04b06bc 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 *
-- 
1.7.3.4