[PATCH v3 00/13] use rbtrees for preliminary backrefs

[PATCH v3 00/13] use rbtrees for preliminary backrefs

[Edmund Nadolski]

This patch series attempts to improve the performance of backref
searches by changing the prelim_refs implementation to use
rbtrees instead of lists.  This also aims to reduce the soft
lockup occurences that can result when a backref search consumes
too much cpu time.

Test runs of btrfs/130 show an improvement in the overall
run time of the test (shown below in seconds) as a function of
the number of extents:

    nr_extents:    256    512    640    1024     2048
    ------------+-------+-----+-------+-------+------
     unpatched:     20    186    375    2204    40419
       patched:     12     93    203    1060    22007

(Note, the current default value for nr_extents in btrfs/130 is
4096, which takes a very long time to complete.)

Changes for v3:

Patch 08/13:
 - Update changelog and comments for third rbtree.
 - Fixed issue in resolve_indirect_refs() which prevented
   module load when sanity checking was enabled.

Patch 10/13:
 - Fix TP_printk_btrfs format string per coding standards.

Changes for v2:

Patch 06/13:
 - Added changelog description.

Patch 07/13:
 - Updated changelog description.
 - Removed 'TODO' comment.

Patch 08/13:
 - Added code for proper iteration of missing keys. This adds
   a third rbtree (.indirect_missing_keys in struct preftrees)
   plus the requisite code in add_prelim_ref(), add_missing_keys(),
   resolve_indirect_refs(), and find_parent_nodes().
 - Rename release_pref() to free_pref().
 - Replace WARN() with BUG_ON().
 - Remove 'TODO' comments and the unused 'merge_mode' enum.

The other patches have no functional changes. Some have diff
context changes due to the above modifications.

Edmund Nadolski (6):
  btrfs: btrfs_check_shared should manage its own transaction
  btrfs: remove ref_tree implementation from backref.c
  btrfs: convert prelimary reference tracking to use rbtrees
  btrfs: add cond_resched() calls when resolving backrefs
  btrfs: allow backref search checks for shared extents
  btrfs: clean up extraneous computations in add_delayed_refs

Jeff Mahoney (7):
  btrfs: struct-funcs, constify readers
  btrfs: constify tracepoint arguments
  btrfs: backref, constify some arguments
  btrfs: backref, add unode_aux_to_inode_list helper
  btrfs: backref, cleanup __ namespace abuse
  btrfs: add a node counter to each of the rbtrees
  btrfs: backref, add tracepoints for prelim_ref insertion and merging

 fs/btrfs/async-thread.c      |    6 +-
 fs/btrfs/async-thread.h      |    6 +-
 fs/btrfs/backref.c           | 1072 ++++++++++++++++++------------------------
 fs/btrfs/backref.h           |   16 +-
 fs/btrfs/btrfs_inode.h       |    4 +-
 fs/btrfs/ctree.h             |  128 ++---
 fs/btrfs/extent_io.c         |   46 +-
 fs/btrfs/extent_io.h         |   19 +-
 fs/btrfs/struct-funcs.c      |    9 +-
 fs/btrfs/super.c             |    1 +
 include/trace/events/btrfs.h |  300 +++++++-----
 11 files changed, 772 insertions(+), 835 deletions(-)

-- 
2.10.2

[PATCH v3 08/13] btrfs: convert prelimary reference tracking to use rbtrees

[Edmund Nadolski]

It's been known for a while that the use of multiple lists
that are periodically merged was an algorithmic problem within
btrfs.  There are several workloads that don't complete in any
reasonable amount of time (e.g. btrfs/130) and others that cause
soft lockups.

The solution is to use a set of rbtrees that do insertion merging
for both indirect and direct refs, with the former converting
refs into the latter.  The result is a btrfs/130 workload that
used to take several hours now takes about half of that. This
runtime still isn't acceptable and a future patch will address that
by moving the rbtrees higher in the stack so the lookups can be
shared across multiple calls to find_parent_nodes.

Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c | 441 ++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 284 insertions(+), 157 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6cac5ab..1edb107 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -26,11 +26,6 @@
 #include "delayed-ref.h"
 #include "locking.h"
 
-enum merge_mode {
-	MERGE_IDENTICAL_KEYS = 1,
-	MERGE_IDENTICAL_PARENTS,
-};
-
 /* Just an arbitrary number so we can be sure this happened */
 #define BACKREF_FOUND_SHARED 6
 
@@ -129,7 +124,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
  * this structure records all encountered refs on the way up to the root
  */
 struct prelim_ref {
-	struct list_head list;
+	struct rb_node rbnode;
 	u64 root_id;
 	struct btrfs_key key_for_search;
 	int level;
@@ -139,6 +134,18 @@ struct prelim_ref {
 	u64 wanted_disk_byte;
 };
 
+struct preftree {
+	struct rb_root root;
+};
+
+#define PREFTREE_INIT	{ .root = RB_ROOT }
+
+struct preftrees {
+	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
+	struct preftree indirect;  /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
+	struct preftree indirect_missing_keys;
+};
+
 static struct kmem_cache *btrfs_prelim_ref_cache;
 
 int __init btrfs_prelim_ref_init(void)
@@ -158,6 +165,108 @@ void btrfs_prelim_ref_exit(void)
 	kmem_cache_destroy(btrfs_prelim_ref_cache);
 }
 
+static void free_pref(struct prelim_ref *ref)
+{
+	kmem_cache_free(btrfs_prelim_ref_cache, ref);
+}
+
+/*
+ * Return 0 when both refs are for the same block (and can be merged).
+ * A -1 return indicates ref1 is a 'lower' block than ref2, while 1
+ * indicates a 'higher' block.
+ */
+static int prelim_ref_compare(struct prelim_ref *ref1,
+			      struct prelim_ref *ref2)
+{
+	if (ref1->level < ref2->level)
+		return -1;
+	if (ref1->level > ref2->level)
+		return 1;
+	if (ref1->root_id < ref2->root_id)
+		return -1;
+	if (ref1->root_id > ref2->root_id)
+		return 1;
+	if (ref1->key_for_search.type < ref2->key_for_search.type)
+		return -1;
+	if (ref1->key_for_search.type > ref2->key_for_search.type)
+		return 1;
+	if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
+		return -1;
+	if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
+		return 1;
+	if (ref1->key_for_search.offset < ref2->key_for_search.offset)
+		return -1;
+	if (ref1->key_for_search.offset > ref2->key_for_search.offset)
+		return 1;
+	if (ref1->parent < ref2->parent)
+		return -1;
+	if (ref1->parent > ref2->parent)
+		return 1;
+
+	return 0;
+}
+
+/*
+ * Add @newref to the @root rbtree, merging identical refs.
+ *
+ * Callers should assumed that newref has been freed after calling.
+ */
+static void prelim_ref_insert(struct preftree *preftree,
+			      struct prelim_ref *newref)
+{
+	struct rb_root *root;
+	struct rb_node **p;
+	struct rb_node *parent = NULL;
+	struct prelim_ref *ref;
+	int result;
+
+	root = &preftree->root;
+	p = &root->rb_node;
+
+	while (*p) {
+		parent = *p;
+		ref = rb_entry(parent, struct prelim_ref, rbnode);
+		result = prelim_ref_compare(ref, newref);
+		if (result < 0) {
+			p = &(*p)->rb_left;
+		} else if (result > 0) {
+			p = &(*p)->rb_right;
+		} else {
+			/* Identical refs, merge them and free @newref */
+			struct extent_inode_elem *eie = ref->inode_list;
+
+			while (eie && eie->next)
+				eie = eie->next;
+
+			if (!eie)
+				ref->inode_list = newref->inode_list;
+			else
+				eie->next = newref->inode_list;
+			ref->count += newref->count;
+			free_pref(newref);
+			return;
+		}
+	}
+
+	rb_link_node(&newref->rbnode, parent, p);
+	rb_insert_color(&newref->rbnode, root);
+}
+
+/*
+ * Release the entire tree.  We don't care about internal consistency so
+ * just free everything and then reset the tree root.
+ */
+static void prelim_release(struct preftree *preftree)
+{
+	struct prelim_ref *ref, *next_ref;
+
+	rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root,
+					     rbnode)
+		free_pref(ref);
+
+	preftree->root = RB_ROOT;
+}
+
 /*
  * the rules for all callers of this function are:
  * - obtaining the parent is the goal
@@ -196,7 +305,7 @@ void btrfs_prelim_ref_exit(void)
  * additional information that's available but not required to find the parent
  * block might help in merging entries to gain some speed.
  */
-static int add_prelim_ref(struct list_head *head, u64 root_id,
+static int add_prelim_ref(struct preftree *preftree, u64 root_id,
 			  const struct btrfs_key *key, int level, u64 parent,
 			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
 {
@@ -243,11 +352,31 @@ static int add_prelim_ref(struct list_head *head, u64 root_id,
 	ref->count = count;
 	ref->parent = parent;
 	ref->wanted_disk_byte = wanted_disk_byte;
-	list_add_tail(&ref->list, head);
+	prelim_ref_insert(preftree, ref);
 
 	return 0;
 }
 
+/* direct refs use root == 0, key == NULL */
+static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
+			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+{
+	return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
+			      wanted_disk_byte, count, gfp_mask);
+}
+
+/* indirect refs use parent == 0 */
+static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
+			    const struct btrfs_key *key, int level,
+			    u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+{
+	struct preftree *tree = &preftrees->indirect;
+	if (!key)
+		tree = &preftrees->indirect_missing_keys;
+	return add_prelim_ref(tree, root_id, key, level, 0,
+			      wanted_disk_byte, count, gfp_mask);
+}
+
 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
 			   struct ulist *parents, struct prelim_ref *ref,
 			   int level, u64 time_seq, const u64 *extent_item_pos,
@@ -429,38 +558,63 @@ unode_aux_to_inode_list(struct ulist_node *node)
 }
 
 /*
- * resolve all indirect backrefs from the list
+ * We maintain three seperate rbtrees: one for direct refs, one for
+ * indirect refs which have a key, and one for indirect refs which do not
+ * have a key. Each tree does merge on insertion.
+ *
+ * Once all of the references are located, we iterate over the tree of
+ * indirect refs with missing keys. An appropriate key is located and
+ * the ref is moved onto the tree for indirect refs. After all missing
+ * keys are thus located, we iterate over the indirect ref tree, resolve
+ * each reference, and then insert the resolved reference onto the
+ * direct tree (merging there too).
+ *
+ * New backrefs (i.e., for parent nodes) are added to the appropriate
+ * rbtree as they are encountered. The new backrefs are subsequently
+ * resolved as above.
  */
 static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 				 struct btrfs_path *path, u64 time_seq,
-				 struct list_head *head,
+				 struct preftrees *preftrees,
 				 const u64 *extent_item_pos, u64 total_refs,
 				 u64 root_objectid)
 {
 	int err;
 	int ret = 0;
-	struct prelim_ref *ref;
-	struct prelim_ref *ref_safe;
-	struct prelim_ref *new_ref;
 	struct ulist *parents;
 	struct ulist_node *node;
 	struct ulist_iterator uiter;
+	struct rb_node *rnode;
 
 	parents = ulist_alloc(GFP_NOFS);
 	if (!parents)
 		return -ENOMEM;
 
 	/*
-	 * _safe allows us to insert directly after the current item without
-	 * iterating over the newly inserted items.
-	 * we're also allowed to re-assign ref during iteration.
+	 * We could trade memory usage for performance here by iterating
+	 * the tree, allocating new refs for each insertion, and then
+	 * freeing the entire indirect tree when we're done.  In some test
+	 * cases, the tree can grow quite large (~200k objects).
 	 */
-	list_for_each_entry_safe(ref, ref_safe, head, list) {
-		if (ref->parent)	/* already direct */
-			continue;
-		if (ref->count == 0)
+	while ((rnode = rb_first(&preftrees->indirect.root))) {
+		struct prelim_ref *ref;
+
+		ref = rb_entry(rnode, struct prelim_ref, rbnode);
+		if (WARN(ref->parent,
+			 "BUG: direct ref found in indirect tree")) {
+			ret = -EINVAL;
+			goto out;
+		}
+
+		rb_erase(&ref->rbnode, &preftrees->indirect.root);
+
+		if (ref->count == 0) {
+			free_pref(ref);
 			continue;
+		}
+
 		if (root_objectid && ref->root_id != root_objectid) {
+			free_pref(ref);
 			ret = BACKREF_FOUND_SHARED;
 			goto out;
 		}
@@ -472,8 +626,10 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		 * and return directly.
 		 */
 		if (err == -ENOENT) {
+			prelim_ref_insert(&preftrees->direct, ref);
 			continue;
 		} else if (err) {
+			free_pref(ref);
 			ret = err;
 			goto out;
 		}
@@ -484,19 +640,26 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		ref->parent = node ? node->val : 0;
 		ref->inode_list = unode_aux_to_inode_list(node);
 
-		/* additional parents require new refs being added here */
+		/* Add a prelim_ref(s) for any other parent(s). */
 		while ((node = ulist_next(parents, &uiter))) {
+			struct prelim_ref *new_ref;
+
 			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
 						   GFP_NOFS);
 			if (!new_ref) {
+				free_pref(ref);
 				ret = -ENOMEM;
 				goto out;
 			}
 			memcpy(new_ref, ref, sizeof(*ref));
 			new_ref->parent = node->val;
 			new_ref->inode_list = unode_aux_to_inode_list(node);
-			list_add(&new_ref->list, &ref->list);
+			prelim_ref_insert(&preftrees->direct, new_ref);
 		}
+
+		/* Now it's a direct ref, put it in the the direct tree */
+		prelim_ref_insert(&preftrees->direct, ref);
+
 		ulist_reinit(parents);
 	}
 out:
@@ -504,44 +667,31 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 	return ret;
 }
 
-static inline int ref_for_same_block(struct prelim_ref *ref1,
-				     struct prelim_ref *ref2)
-{
-	if (ref1->level != ref2->level)
-		return 0;
-	if (ref1->root_id != ref2->root_id)
-		return 0;
-	if (ref1->key_for_search.type != ref2->key_for_search.type)
-		return 0;
-	if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
-		return 0;
-	if (ref1->key_for_search.offset != ref2->key_for_search.offset)
-		return 0;
-	if (ref1->parent != ref2->parent)
-		return 0;
-
-	return 1;
-}
-
 /*
  * read tree blocks and add keys where required.
  */
 static int add_missing_keys(struct btrfs_fs_info *fs_info,
-			    struct list_head *head)
+			    struct preftrees *preftrees)
 {
 	struct prelim_ref *ref;
 	struct extent_buffer *eb;
+	struct preftree *tree = &preftrees->indirect_missing_keys;
+	struct rb_node *node;
 
-	list_for_each_entry(ref, head, list) {
-		if (ref->parent)
-			continue;
-		if (ref->key_for_search.type)
-			continue;
+	while ((node = rb_first(&tree->root))) {
+		ref = rb_entry(node, struct prelim_ref, rbnode);
+		rb_erase(node, &tree->root);
+
+		BUG_ON(ref->parent);	/* should not be a direct ref */
+		BUG_ON(ref->key_for_search.type);
 		BUG_ON(!ref->wanted_disk_byte);
+
 		eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
 		if (IS_ERR(eb)) {
+			free_pref(ref);
 			return PTR_ERR(eb);
 		} else if (!extent_buffer_uptodate(eb)) {
+			free_pref(ref);
 			free_extent_buffer(eb);
 			return -EIO;
 		}
@@ -552,73 +702,31 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
 			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
 		btrfs_tree_read_unlock(eb);
 		free_extent_buffer(eb);
+		prelim_ref_insert(&preftrees->indirect, ref);
 	}
 	return 0;
 }
 
 /*
- * merge backrefs and adjust counts accordingly
- *
- *    FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref
- *           then we can merge more here. Additionally, we could even add a key
- *           range for the blocks we looked into to merge even more (-> replace
- *           unresolved refs by those having a parent).
- */
-static void merge_refs(struct list_head *head, enum merge_mode mode)
-{
-	struct prelim_ref *pos1;
-
-	list_for_each_entry(pos1, head, list) {
-		struct prelim_ref *pos2 = pos1, *tmp;
-
-		list_for_each_entry_safe_continue(pos2, tmp, head, list) {
-			struct prelim_ref *ref1 = pos1, *ref2 = pos2;
-			struct extent_inode_elem *eie;
-
-			if (!ref_for_same_block(ref1, ref2))
-				continue;
-			if (mode == MERGE_IDENTICAL_KEYS) {
-				if (!ref1->parent && ref2->parent)
-					swap(ref1, ref2);
-			} else {
-				if (ref1->parent != ref2->parent)
-					continue;
-			}
-
-			eie = ref1->inode_list;
-			while (eie && eie->next)
-				eie = eie->next;
-			if (eie)
-				eie->next = ref2->inode_list;
-			else
-				ref1->inode_list = ref2->inode_list;
-			ref1->count += ref2->count;
-
-			list_del(&ref2->list);
-			kmem_cache_free(btrfs_prelim_ref_cache, ref2);
-			cond_resched();
-		}
-
-	}
-}
-
-/*
  * add all currently queued delayed refs from this head whose seq nr is
  * smaller or equal that seq to the list
  */
 static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
-			    struct list_head *prefs, u64 *total_refs,
+			    struct preftrees *preftrees, u64 *total_refs,
 			    u64 inum)
 {
 	struct btrfs_delayed_ref_node *node;
 	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
 	struct btrfs_key key;
-	struct btrfs_key op_key = {0};
+	struct btrfs_key tmp_op_key;
+	struct btrfs_key *op_key = NULL;
 	int sgn;
 	int ret = 0;
 
-	if (extent_op && extent_op->update_key)
-		btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
+	if (extent_op && extent_op->update_key) {
+		btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key);
+		op_key = &tmp_op_key;
+	}
 
 	spin_lock(&head->lock);
 	list_for_each_entry(node, &head->ref_list, list) {
@@ -642,24 +750,30 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 		*total_refs += (node->ref_mod * sgn);
 		switch (node->type) {
 		case BTRFS_TREE_BLOCK_REF_KEY: {
+			/* NORMAL INDIRECT METADATA backref */
 			struct btrfs_delayed_tree_ref *ref;
 
 			ref = btrfs_delayed_node_to_tree_ref(node);
-			ret = add_prelim_ref(prefs, ref->root, &op_key,
-					     ref->level + 1, 0, node->bytenr,
-					     node->ref_mod * sgn, GFP_ATOMIC);
+			ret = add_indirect_ref(preftrees, ref->root, &tmp_op_key,
+					       ref->level + 1, node->bytenr,
+					       node->ref_mod * sgn,
+					       GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_BLOCK_REF_KEY: {
+			/* SHARED DIRECT METADATA backref */
 			struct btrfs_delayed_tree_ref *ref;
 
 			ref = btrfs_delayed_node_to_tree_ref(node);
-			ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1,
+
+			ret = add_direct_ref(preftrees, ref->level + 1,
 					     ref->parent, node->bytenr,
-					     node->ref_mod * sgn, GFP_ATOMIC);
+					     node->ref_mod * sgn,
+					     GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_EXTENT_DATA_REF_KEY: {
+			/* NORMAL INDIRECT DATA backref */
 			struct btrfs_delayed_data_ref *ref;
 			ref = btrfs_delayed_node_to_data_ref(node);
 
@@ -676,17 +790,21 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 				break;
 			}
 
-			ret = add_prelim_ref(prefs, ref->root, &key, 0, 0,
-					     node->bytenr, node->ref_mod * sgn,
-					     GFP_ATOMIC);
+			ret = add_indirect_ref(preftrees, ref->root, &key, 0,
+					       node->bytenr,
+					       node->ref_mod * sgn,
+					       GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_DATA_REF_KEY: {
+			/* SHARED DIRECT FULL backref */
 			struct btrfs_delayed_data_ref *ref;
 
 			ref = btrfs_delayed_node_to_data_ref(node);
-			ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent,
-					     node->bytenr, node->ref_mod * sgn,
+
+			ret = add_direct_ref(preftrees, 0, ref->parent,
+					     node->bytenr,
+					     node->ref_mod * sgn,
 					     GFP_ATOMIC);
 			break;
 		}
@@ -704,7 +822,7 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
  * add all inline backrefs for bytenr to the list
  */
 static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
-			   int *info_level, struct list_head *prefs,
+			   int *info_level, struct preftrees *preftrees,
 			   u64 *total_refs, u64 inum)
 {
 	int ret = 0;
@@ -760,8 +878,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 
 		switch (type) {
 		case BTRFS_SHARED_BLOCK_REF_KEY:
-			ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1,
-					     offset, bytenr, 1, GFP_NOFS);
+			ret = add_direct_ref(preftrees, *info_level + 1, offset,
+					     bytenr, 1, GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
 			struct btrfs_shared_data_ref *sdref;
@@ -769,14 +887,15 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 
 			sdref = (struct btrfs_shared_data_ref *)(iref + 1);
 			count = btrfs_shared_data_ref_count(leaf, sdref);
-			ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
+
+			ret = add_direct_ref(preftrees, 0, offset,
 					     bytenr, count, GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
-			ret = add_prelim_ref(prefs, offset, NULL,
-					     *info_level + 1, 0,
-					     bytenr, 1, GFP_NOFS);
+			ret = add_indirect_ref(preftrees, offset, NULL,
+					       *info_level + 1, bytenr, 1,
+					       GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
 			struct btrfs_extent_data_ref *dref;
@@ -796,8 +915,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 			}
 
 			root = btrfs_extent_data_ref_root(leaf, dref);
-			ret = add_prelim_ref(prefs, root, &key, 0, 0,
-					     bytenr, count, GFP_NOFS);
+
+			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
+					       count, GFP_NOFS);
 			break;
 		}
 		default:
@@ -816,7 +936,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
  */
 static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			  struct btrfs_path *path, u64 bytenr,
-			  int info_level, struct list_head *prefs, u64 inum)
+			  int info_level, struct preftrees *preftrees,
+			  u64 inum)
 {
 	struct btrfs_root *extent_root = fs_info->extent_root;
 	int ret;
@@ -846,26 +967,31 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 
 		switch (key.type) {
 		case BTRFS_SHARED_BLOCK_REF_KEY:
-			ret = add_prelim_ref(prefs, 0, NULL, info_level + 1,
-					     key.offset, bytenr, 1, GFP_NOFS);
+			/* SHARED DIRECT METADATA backref */
+			ret = add_direct_ref(preftrees, info_level + 1,
+					     key.offset, bytenr, 1,
+					     GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
+			/* SHARED DIRECT FULL backref */
 			struct btrfs_shared_data_ref *sdref;
 			int count;
 
 			sdref = btrfs_item_ptr(leaf, slot,
 					      struct btrfs_shared_data_ref);
 			count = btrfs_shared_data_ref_count(leaf, sdref);
-			ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
-					     bytenr, count, GFP_NOFS);
+			ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
+					     count, GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
-			ret = add_prelim_ref(prefs, key.offset, NULL,
-					     info_level + 1, 0,
-					     bytenr, 1, GFP_NOFS);
+			/* NORMAL INDIRECT METADATA backref */
+			ret = add_indirect_ref(preftrees, key.offset, NULL,
+					       info_level + 1, bytenr, 1,
+					       GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
+			/* NORMAL INDIRECT DATA backref */
 			struct btrfs_extent_data_ref *dref;
 			int count;
 			u64 root;
@@ -884,8 +1010,8 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			}
 
 			root = btrfs_extent_data_ref_root(leaf, dref);
-			ret = add_prelim_ref(prefs, root, &key, 0, 0,
-					     bytenr, count, GFP_NOFS);
+			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
+					       count, GFP_NOFS);
 			break;
 		}
 		default:
@@ -926,14 +1052,16 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 	struct btrfs_delayed_ref_head *head;
 	int info_level = 0;
 	int ret;
-	struct list_head prefs_delayed;
-	struct list_head prefs;
 	struct prelim_ref *ref;
+	struct rb_node *node;
 	struct extent_inode_elem *eie = NULL;
+	/* total of both direct AND indirect refs! */
 	u64 total_refs = 0;
-
-	INIT_LIST_HEAD(&prefs);
-	INIT_LIST_HEAD(&prefs_delayed);
+	struct preftrees preftrees = {
+		.direct = PREFTREE_INIT,
+		.indirect = PREFTREE_INIT,
+		.indirect_missing_keys = PREFTREE_INIT
+	};
 
 	key.objectid = bytenr;
 	key.offset = (u64)-1;
@@ -996,9 +1124,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 				goto again;
 			}
 			spin_unlock(&delayed_refs->lock);
-			ret = add_delayed_refs(head, time_seq,
-					       &prefs_delayed, &total_refs,
-					       inum);
+			ret = add_delayed_refs(head, time_seq, &preftrees,
+					       &total_refs, inum);
 			mutex_unlock(&head->mutex);
 			if (ret)
 				goto out;
@@ -1019,35 +1146,43 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
 		     key.type == BTRFS_METADATA_ITEM_KEY)) {
 			ret = add_inline_refs(path, bytenr, &info_level,
-					      &prefs, &total_refs, inum);
+					      &preftrees, &total_refs, inum);
 			if (ret)
 				goto out;
 			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
-					     &prefs, inum);
+					     &preftrees, inum);
 			if (ret)
 				goto out;
 		}
 	}
-	btrfs_release_path(path);
 
-	list_splice_init(&prefs_delayed, &prefs);
+	btrfs_release_path(path);
 
-	ret = add_missing_keys(fs_info, &prefs);
+	ret = add_missing_keys(fs_info, &preftrees);
 	if (ret)
 		goto out;
 
-	merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
+	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
 
-	ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs,
+	ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
 				    extent_item_pos, total_refs,
 				    root_objectid);
 	if (ret)
 		goto out;
 
-	merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
+	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root));
 
-	while (!list_empty(&prefs)) {
-		ref = list_first_entry(&prefs, struct prelim_ref, list);
+	/*
+	 * This walks the tree of merged and resolved refs. Tree blocks are
+	 * read in as needed. Unique entries are added to the ulist, and
+	 * the list of found roots is updated.
+	 *
+	 * We release the entire tree in one go before returning.
+	 */
+	node = rb_first(&preftrees.direct.root);
+	while (node) {
+		ref = rb_entry(node, struct prelim_ref, rbnode);
+		node = rb_next(&ref->rbnode);
 		WARN_ON(ref->count < 0);
 		if (roots && ref->count && ref->root_id && ref->parent == 0) {
 			if (root_objectid && ref->root_id != root_objectid) {
@@ -1101,23 +1236,15 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 			}
 			eie = NULL;
 		}
-		list_del(&ref->list);
-		kmem_cache_free(btrfs_prelim_ref_cache, ref);
 	}
 
 out:
 	btrfs_free_path(path);
-	while (!list_empty(&prefs)) {
-		ref = list_first_entry(&prefs, struct prelim_ref, list);
-		list_del(&ref->list);
-		kmem_cache_free(btrfs_prelim_ref_cache, ref);
-	}
-	while (!list_empty(&prefs_delayed)) {
-		ref = list_first_entry(&prefs_delayed, struct prelim_ref,
-				       list);
-		list_del(&ref->list);
-		kmem_cache_free(btrfs_prelim_ref_cache, ref);
-	}
+
+	prelim_release(&preftrees.direct);
+	prelim_release(&preftrees.indirect);
+	prelim_release(&preftrees.indirect_missing_keys);
+
 	if (ret < 0)
 		free_inode_elem_list(eie);
 	return ret;
-- 
2.10.2

[PATCH v3 09/13] btrfs: add a node counter to each of the rbtrees

[Edmund Nadolski]

From: Jeff Mahoney <jeffm@suse.com>

This patch adds counters to each of the rbtrees so that we can tell
how large they are growing for a given workload.  These counters
will be exported by tracepoints in the next patch.

Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 1edb107..2e452264 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -136,9 +136,10 @@ struct prelim_ref {
 
 struct preftree {
 	struct rb_root root;
+	unsigned int count;
 };
 
-#define PREFTREE_INIT	{ .root = RB_ROOT }
+#define PREFTREE_INIT	{ .root = RB_ROOT, .count = 0 }
 
 struct preftrees {
 	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
@@ -248,6 +249,7 @@ static void prelim_ref_insert(struct preftree *preftree,
 		}
 	}
 
+	preftree->count++;
 	rb_link_node(&newref->rbnode, parent, p);
 	rb_insert_color(&newref->rbnode, root);
 }
@@ -265,6 +267,7 @@ static void prelim_release(struct preftree *preftree)
 		free_pref(ref);
 
 	preftree->root = RB_ROOT;
+	preftree->count = 0;
 }
 
 /*
@@ -607,6 +610,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		}
 
 		rb_erase(&ref->rbnode, &preftrees->indirect.root);
+		preftrees->indirect.count--;
 
 		if (ref->count == 0) {
 			free_pref(ref);
-- 
2.10.2

[PATCH v3 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging

[Edmund Nadolski]

From: Jeff Mahoney <jeffm@suse.com>

This patch adds a tracepoint event for prelim_ref insertion and
merging.  For each, the ref being inserted or merged and the count
of tree nodes is issued.

Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c           | 119 ++++++++++++++++++++++---------------------
 fs/btrfs/backref.h           |  12 +++++
 fs/btrfs/super.c             |   1 +
 include/trace/events/btrfs.h |  58 +++++++++++++++++++++
 4 files changed, 132 insertions(+), 58 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 2e452264..19c9e92 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -26,6 +26,8 @@
 #include "delayed-ref.h"
 #include "locking.h"
 
+#include <trace/events/btrfs.h>
+
 /* Just an arbitrary number so we can be sure this happened */
 #define BACKREF_FOUND_SHARED 6
 
@@ -120,20 +122,6 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
 	return 0;
 }
 
-/*
- * this structure records all encountered refs on the way up to the root
- */
-struct prelim_ref {
-	struct rb_node rbnode;
-	u64 root_id;
-	struct btrfs_key key_for_search;
-	int level;
-	int count;
-	struct extent_inode_elem *inode_list;
-	u64 parent;
-	u64 wanted_disk_byte;
-};
-
 struct preftree {
 	struct rb_root root;
 	unsigned int count;
@@ -212,7 +200,8 @@ static int prelim_ref_compare(struct prelim_ref *ref1,
  *
  * Callers should assumed that newref has been freed after calling.
  */
-static void prelim_ref_insert(struct preftree *preftree,
+static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
+			      struct preftree *preftree,
 			      struct prelim_ref *newref)
 {
 	struct rb_root *root;
@@ -243,6 +232,8 @@ static void prelim_ref_insert(struct preftree *preftree,
 				ref->inode_list = newref->inode_list;
 			else
 				eie->next = newref->inode_list;
+			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
+						     preftree->count);
 			ref->count += newref->count;
 			free_pref(newref);
 			return;
@@ -250,6 +241,7 @@ static void prelim_ref_insert(struct preftree *preftree,
 	}
 
 	preftree->count++;
+	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
 	rb_link_node(&newref->rbnode, parent, p);
 	rb_insert_color(&newref->rbnode, root);
 }
@@ -308,7 +300,8 @@ static void prelim_release(struct preftree *preftree)
  * additional information that's available but not required to find the parent
  * block might help in merging entries to gain some speed.
  */
-static int add_prelim_ref(struct preftree *preftree, u64 root_id,
+static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
+			  struct preftree *preftree, u64 root_id,
 			  const struct btrfs_key *key, int level, u64 parent,
 			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
 {
@@ -355,28 +348,30 @@ static int add_prelim_ref(struct preftree *preftree, u64 root_id,
 	ref->count = count;
 	ref->parent = parent;
 	ref->wanted_disk_byte = wanted_disk_byte;
-	prelim_ref_insert(preftree, ref);
+	prelim_ref_insert(fs_info, preftree, ref);
 
 	return 0;
 }
 
 /* direct refs use root == 0, key == NULL */
-static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
+static int add_direct_ref(const struct btrfs_fs_info *fs_info,
+			  struct preftrees *preftrees, int level, u64 parent,
 			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
 {
-	return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
-			      wanted_disk_byte, count, gfp_mask);
+	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
+			      parent, wanted_disk_byte, count, gfp_mask);
 }
 
 /* indirect refs use parent == 0 */
-static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
+static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
+			    struct preftrees *preftrees, u64 root_id,
 			    const struct btrfs_key *key, int level,
 			    u64 wanted_disk_byte, int count, gfp_t gfp_mask)
 {
 	struct preftree *tree = &preftrees->indirect;
 	if (!key)
 		tree = &preftrees->indirect_missing_keys;
-	return add_prelim_ref(tree, root_id, key, level, 0,
+	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
 			      wanted_disk_byte, count, gfp_mask);
 }
 
@@ -630,7 +625,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		 * and return directly.
 		 */
 		if (err == -ENOENT) {
-			prelim_ref_insert(&preftrees->direct, ref);
+			prelim_ref_insert(fs_info, &preftrees->direct, ref);
 			continue;
 		} else if (err) {
 			free_pref(ref);
@@ -658,11 +653,11 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 			memcpy(new_ref, ref, sizeof(*ref));
 			new_ref->parent = node->val;
 			new_ref->inode_list = unode_aux_to_inode_list(node);
-			prelim_ref_insert(&preftrees->direct, new_ref);
+			prelim_ref_insert(fs_info, &preftrees->direct, new_ref);
 		}
 
 		/* Now it's a direct ref, put it in the the direct tree */
-		prelim_ref_insert(&preftrees->direct, ref);
+		prelim_ref_insert(fs_info, &preftrees->direct, ref);
 
 		ulist_reinit(parents);
 	}
@@ -706,7 +701,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
 			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
 		btrfs_tree_read_unlock(eb);
 		free_extent_buffer(eb);
-		prelim_ref_insert(&preftrees->indirect, ref);
+		prelim_ref_insert(fs_info, &preftrees->indirect, ref);
 	}
 	return 0;
 }
@@ -715,7 +710,8 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
  * add all currently queued delayed refs from this head whose seq nr is
  * smaller or equal that seq to the list
  */
-static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
+static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
+			    struct btrfs_delayed_ref_head *head, u64 seq,
 			    struct preftrees *preftrees, u64 *total_refs,
 			    u64 inum)
 {
@@ -758,8 +754,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 			struct btrfs_delayed_tree_ref *ref;
 
 			ref = btrfs_delayed_node_to_tree_ref(node);
-			ret = add_indirect_ref(preftrees, ref->root, &tmp_op_key,
-					       ref->level + 1, node->bytenr,
+			ret = add_indirect_ref(fs_info, preftrees, ref->root,
+					       &tmp_op_key, ref->level + 1,
+					       node->bytenr,
 					       node->ref_mod * sgn,
 					       GFP_ATOMIC);
 			break;
@@ -770,9 +767,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 
 			ref = btrfs_delayed_node_to_tree_ref(node);
 
-			ret = add_direct_ref(preftrees, ref->level + 1,
-					     ref->parent, node->bytenr,
-					     node->ref_mod * sgn,
+			ret = add_direct_ref(fs_info, preftrees,
+					     ref->level + 1, ref->parent,
+					     node->bytenr, node->ref_mod * sgn,
 					     GFP_ATOMIC);
 			break;
 		}
@@ -794,8 +791,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 				break;
 			}
 
-			ret = add_indirect_ref(preftrees, ref->root, &key, 0,
-					       node->bytenr,
+			ret = add_indirect_ref(fs_info, preftrees, ref->root,
+					       &key, 0, node->bytenr,
 					       node->ref_mod * sgn,
 					       GFP_ATOMIC);
 			break;
@@ -806,8 +803,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 
 			ref = btrfs_delayed_node_to_data_ref(node);
 
-			ret = add_direct_ref(preftrees, 0, ref->parent,
-					     node->bytenr,
+			ret = add_direct_ref(fs_info, preftrees, 0,
+					     ref->parent, node->bytenr,
 					     node->ref_mod * sgn,
 					     GFP_ATOMIC);
 			break;
@@ -825,7 +822,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 /*
  * add all inline backrefs for bytenr to the list
  */
-static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
+static int add_inline_refs(const struct btrfs_fs_info *fs_info,
+			   struct btrfs_path *path, u64 bytenr,
 			   int *info_level, struct preftrees *preftrees,
 			   u64 *total_refs, u64 inum)
 {
@@ -882,7 +880,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 
 		switch (type) {
 		case BTRFS_SHARED_BLOCK_REF_KEY:
-			ret = add_direct_ref(preftrees, *info_level + 1, offset,
+			ret = add_direct_ref(fs_info, preftrees,
+					     *info_level + 1, offset,
 					     bytenr, 1, GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
@@ -892,14 +891,14 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 			sdref = (struct btrfs_shared_data_ref *)(iref + 1);
 			count = btrfs_shared_data_ref_count(leaf, sdref);
 
-			ret = add_direct_ref(preftrees, 0, offset,
+			ret = add_direct_ref(fs_info, preftrees, 0, offset,
 					     bytenr, count, GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
-			ret = add_indirect_ref(preftrees, offset, NULL,
-					       *info_level + 1, bytenr, 1,
-					       GFP_NOFS);
+			ret = add_indirect_ref(fs_info, preftrees, offset,
+					       NULL, *info_level + 1,
+					       bytenr, 1, GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
 			struct btrfs_extent_data_ref *dref;
@@ -920,8 +919,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
 
 			root = btrfs_extent_data_ref_root(leaf, dref);
 
-			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
-					       count, GFP_NOFS);
+			ret = add_indirect_ref(fs_info, preftrees, root,
+					       &key, 0, bytenr, count,
+					       GFP_NOFS);
 			break;
 		}
 		default:
@@ -972,9 +972,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 		switch (key.type) {
 		case BTRFS_SHARED_BLOCK_REF_KEY:
 			/* SHARED DIRECT METADATA backref */
-			ret = add_direct_ref(preftrees, info_level + 1,
-					     key.offset, bytenr, 1,
-					     GFP_NOFS);
+			ret = add_direct_ref(fs_info, preftrees,
+					     info_level + 1, key.offset,
+					     bytenr, 1, GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
 			/* SHARED DIRECT FULL backref */
@@ -984,15 +984,16 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			sdref = btrfs_item_ptr(leaf, slot,
 					      struct btrfs_shared_data_ref);
 			count = btrfs_shared_data_ref_count(leaf, sdref);
-			ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
-					     count, GFP_NOFS);
+			ret = add_direct_ref(fs_info, preftrees, 0,
+					     key.offset, bytenr, count,
+					     GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
 			/* NORMAL INDIRECT METADATA backref */
-			ret = add_indirect_ref(preftrees, key.offset, NULL,
-					       info_level + 1, bytenr, 1,
-					       GFP_NOFS);
+			ret = add_indirect_ref(fs_info, preftrees, key.offset,
+					       NULL, info_level + 1, bytenr,
+					       1, GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
 			/* NORMAL INDIRECT DATA backref */
@@ -1014,8 +1015,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			}
 
 			root = btrfs_extent_data_ref_root(leaf, dref);
-			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
-					       count, GFP_NOFS);
+			ret = add_indirect_ref(fs_info, preftrees, root,
+					       &key, 0, bytenr, count,
+					       GFP_NOFS);
 			break;
 		}
 		default:
@@ -1128,8 +1130,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 				goto again;
 			}
 			spin_unlock(&delayed_refs->lock);
-			ret = add_delayed_refs(head, time_seq, &preftrees,
-					       &total_refs, inum);
+			ret = add_delayed_refs(fs_info, head, time_seq,
+					       &preftrees, &total_refs, inum);
 			mutex_unlock(&head->mutex);
 			if (ret)
 				goto out;
@@ -1149,8 +1151,9 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 		if (key.objectid == bytenr &&
 		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
 		     key.type == BTRFS_METADATA_ITEM_KEY)) {
-			ret = add_inline_refs(path, bytenr, &info_level,
-					      &preftrees, &total_refs, inum);
+			ret = add_inline_refs(fs_info, path, bytenr,
+					      &info_level, &preftrees,
+					      &total_refs, inum);
 			if (ret)
 				goto out;
 			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index f9428aa..e410335 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -72,4 +72,16 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr);
 
 int __init btrfs_prelim_ref_init(void);
 void btrfs_prelim_ref_exit(void);
+
+struct prelim_ref {
+	struct rb_node rbnode;
+	u64 root_id;
+	struct btrfs_key key_for_search;
+	int level;
+	int count;
+	struct extent_inode_elem *inode_list;
+	u64 parent;
+	u64 wanted_disk_byte;
+};
+
 #endif
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 74e4779..83f2d8c 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -61,6 +61,7 @@
 #include "tests/btrfs-tests.h"
 
 #include "qgroup.h"
+#include "backref.h"
 #define CREATE_TRACE_POINTS
 #include <trace/events/btrfs.h>
 
diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h
index 42560fe..f6aeee1 100644
--- a/include/trace/events/btrfs.h
+++ b/include/trace/events/btrfs.h
@@ -26,6 +26,7 @@ struct btrfs_work;
 struct __btrfs_workqueue;
 struct btrfs_qgroup_extent_record;
 struct btrfs_qgroup;
+struct prelim_ref;
 
 #define show_ref_type(type)						\
 	__print_symbolic(type,						\
@@ -1636,6 +1637,63 @@ TRACE_EVENT(qgroup_meta_reserve,
 		show_root_type(__entry->refroot), __entry->diff)
 );
 
+DECLARE_EVENT_CLASS(btrfs__prelim_ref,
+	TP_PROTO(const struct btrfs_fs_info *fs_info,
+		 const struct prelim_ref *oldref,
+		 const struct prelim_ref *newref, u64 tree_size),
+	TP_ARGS(fs_info, newref, oldref, tree_size),
+
+	TP_STRUCT__entry_btrfs(
+		__field(	u64,  root_id		)
+		__field(	u64,  objectid		)
+		__field(	 u8,  type		)
+		__field(	u64,  offset		)
+		__field(	int,  level		)
+		__field(	int,  old_count		)
+		__field(	u64,  parent		)
+		__field(	u64,  bytenr		)
+		__field(	int,  mod_count		)
+		__field(	u64, tree_size		)
+	),
+
+	TP_fast_assign_btrfs(fs_info,
+		__entry->root_id	= oldref->root_id;
+		__entry->objectid	= oldref->key_for_search.objectid;
+		__entry->type		= oldref->key_for_search.type;
+		__entry->offset		= oldref->key_for_search.offset;
+		__entry->level		= oldref->level;
+		__entry->old_count	= oldref->count;
+		__entry->parent		= oldref->parent;
+		__entry->bytenr		= oldref->wanted_disk_byte;
+		__entry->mod_count	= newref ? newref->count : 0;
+		__entry->tree_size	= tree_size;
+	),
+
+	TP_printk_btrfs("root_id=%llu key=[%llu %u %llu] level=%d count=[%d+%d=%d] parent=%llu wanted_disk_byte=%llu nodes=%llu",
+			(unsigned long long)__entry->root_id,
+			(unsigned long long)__entry->objectid, __entry->type,
+			(unsigned long long)__entry->offset, __entry->level,
+			__entry->old_count, __entry->mod_count,
+			__entry->old_count + __entry->mod_count,
+			(unsigned long long)__entry->parent,
+			(unsigned long long)__entry->bytenr,
+			(unsigned long long)__entry->tree_size)
+);
+
+DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_merge,
+	TP_PROTO(const struct btrfs_fs_info *fs_info,
+		 const struct prelim_ref *oldref,
+		 const struct prelim_ref *newref, u64 tree_size),
+	TP_ARGS(fs_info, oldref, newref, tree_size)
+);
+
+DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_insert,
+	TP_PROTO(const struct btrfs_fs_info *fs_info,
+		 const struct prelim_ref *oldref,
+		 const struct prelim_ref *newref, u64 tree_size),
+	TP_ARGS(fs_info, oldref, newref, tree_size)
+);
+
 #endif /* _TRACE_BTRFS_H */
 
 /* This part must be outside protection */
-- 
2.10.2

[PATCH v3 11/13] btrfs: add cond_resched() calls when resolving backrefs

[Edmund Nadolski]

Since backref resolution is CPU-intensive, the cond_resched calls
should help alleviate soft lockup occurences.

Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 19c9e92..c1882e5 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -660,6 +660,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		prelim_ref_insert(fs_info, &preftrees->direct, ref);
 
 		ulist_reinit(parents);
+		cond_resched();
 	}
 out:
 	ulist_free(parents);
@@ -702,6 +703,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
 		btrfs_tree_read_unlock(eb);
 		free_extent_buffer(eb);
 		prelim_ref_insert(fs_info, &preftrees->indirect, ref);
+		cond_resched();
 	}
 	return 0;
 }
@@ -1243,6 +1245,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 			}
 			eie = NULL;
 		}
+		cond_resched();
 	}
 
 out:
-- 
2.10.2

[PATCH v3 12/13] btrfs: allow backref search checks for shared extents

[Edmund Nadolski]

When called with a struct share_check, find_parent_nodes()
will detect a shared extent and immediately return with
BACKREF_SHARED_FOUND.

Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c | 164 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 115 insertions(+), 49 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index c1882e5..35ac0bd 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -135,6 +135,25 @@ struct preftrees {
 	struct preftree indirect_missing_keys;
 };
 
+/*
+ * Checks for a shared extent during backref search.
+ *
+ * The share_count tracks prelim_refs (direct and indirect) having a
+ * ref->count >0:
+ *  - incremented when a ref->count transitions to >0
+ *  - decremented when a ref->count transitions to <1
+ */
+struct share_check {
+	u64 root_objectid;
+	u64 inum;
+	int share_count;
+};
+
+static inline int extent_is_shared(struct share_check *sc)
+{
+	return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;
+}
+
 static struct kmem_cache *btrfs_prelim_ref_cache;
 
 int __init btrfs_prelim_ref_init(void)
@@ -195,14 +214,26 @@ static int prelim_ref_compare(struct prelim_ref *ref1,
 	return 0;
 }
 
+void update_share_count(struct share_check *sc, int oldcount, int newcount)
+{
+	if ((!sc) || (oldcount == 0 && newcount < 1))
+		return;
+
+	if (oldcount > 0 && newcount < 1)
+		sc->share_count--;
+	else if (oldcount < 1 && newcount > 0)
+		sc->share_count++;
+}
+
 /*
  * Add @newref to the @root rbtree, merging identical refs.
  *
- * Callers should assumed that newref has been freed after calling.
+ * Callers should assume that newref has been freed after calling.
  */
 static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
 			      struct preftree *preftree,
-			      struct prelim_ref *newref)
+			      struct prelim_ref *newref,
+			      struct share_check *sc)
 {
 	struct rb_root *root;
 	struct rb_node **p;
@@ -234,12 +265,20 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
 				eie->next = newref->inode_list;
 			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
 						     preftree->count);
+			/*
+			 * A delayed ref can have newref->count < 0.
+			 * The ref->count is updated to follow any
+			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
+			 */
+			update_share_count(sc, ref->count,
+					   ref->count + newref->count);
 			ref->count += newref->count;
 			free_pref(newref);
 			return;
 		}
 	}
 
+	update_share_count(sc, 0, newref->count);
 	preftree->count++;
 	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
 	rb_link_node(&newref->rbnode, parent, p);
@@ -303,7 +342,8 @@ static void prelim_release(struct preftree *preftree)
 static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
 			  struct preftree *preftree, u64 root_id,
 			  const struct btrfs_key *key, int level, u64 parent,
-			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+			  u64 wanted_disk_byte, int count,
+			  struct share_check *sc, gfp_t gfp_mask)
 {
 	struct prelim_ref *ref;
 
@@ -348,31 +388,32 @@ static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
 	ref->count = count;
 	ref->parent = parent;
 	ref->wanted_disk_byte = wanted_disk_byte;
-	prelim_ref_insert(fs_info, preftree, ref);
-
-	return 0;
+	prelim_ref_insert(fs_info, preftree, ref, sc);
+	return extent_is_shared(sc);
 }
 
 /* direct refs use root == 0, key == NULL */
 static int add_direct_ref(const struct btrfs_fs_info *fs_info,
 			  struct preftrees *preftrees, int level, u64 parent,
-			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+			  u64 wanted_disk_byte, int count,
+			  struct share_check *sc, gfp_t gfp_mask)
 {
 	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
-			      parent, wanted_disk_byte, count, gfp_mask);
+			      parent, wanted_disk_byte, count, sc, gfp_mask);
 }
 
 /* indirect refs use parent == 0 */
 static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
 			    struct preftrees *preftrees, u64 root_id,
 			    const struct btrfs_key *key, int level,
-			    u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+			    u64 wanted_disk_byte, int count,
+			    struct share_check *sc, gfp_t gfp_mask)
 {
 	struct preftree *tree = &preftrees->indirect;
 	if (!key)
 		tree = &preftrees->indirect_missing_keys;
 	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
-			      wanted_disk_byte, count, gfp_mask);
+			      wanted_disk_byte, count, sc, gfp_mask);
 }
 
 static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
@@ -575,7 +616,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 				 struct btrfs_path *path, u64 time_seq,
 				 struct preftrees *preftrees,
 				 const u64 *extent_item_pos, u64 total_refs,
-				 u64 root_objectid)
+				 struct share_check *sc)
 {
 	int err;
 	int ret = 0;
@@ -612,7 +653,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 			continue;
 		}
 
-		if (root_objectid && ref->root_id != root_objectid) {
+		if (sc && sc->root_objectid &&
+		    ref->root_id != sc->root_objectid) {
 			free_pref(ref);
 			ret = BACKREF_FOUND_SHARED;
 			goto out;
@@ -625,7 +667,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 		 * and return directly.
 		 */
 		if (err == -ENOENT) {
-			prelim_ref_insert(fs_info, &preftrees->direct, ref);
+			prelim_ref_insert(fs_info, &preftrees->direct, ref,
+					  NULL);
 			continue;
 		} else if (err) {
 			free_pref(ref);
@@ -653,11 +696,15 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 			memcpy(new_ref, ref, sizeof(*ref));
 			new_ref->parent = node->val;
 			new_ref->inode_list = unode_aux_to_inode_list(node);
-			prelim_ref_insert(fs_info, &preftrees->direct, new_ref);
+			prelim_ref_insert(fs_info, &preftrees->direct,
+					  new_ref, NULL);
 		}
 
-		/* Now it's a direct ref, put it in the the direct tree */
-		prelim_ref_insert(fs_info, &preftrees->direct, ref);
+		/*
+		 * Now it's a direct ref, put it in the the direct tree. We must
+		 * do this last because the ref could be merged/freed here.
+		 */
+		prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL);
 
 		ulist_reinit(parents);
 		cond_resched();
@@ -702,7 +749,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
 			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
 		btrfs_tree_read_unlock(eb);
 		free_extent_buffer(eb);
-		prelim_ref_insert(fs_info, &preftrees->indirect, ref);
+		prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);
 		cond_resched();
 	}
 	return 0;
@@ -715,7 +762,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
 static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			    struct btrfs_delayed_ref_head *head, u64 seq,
 			    struct preftrees *preftrees, u64 *total_refs,
-			    u64 inum)
+			    struct share_check *sc)
 {
 	struct btrfs_delayed_ref_node *node;
 	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
@@ -760,7 +807,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 					       &tmp_op_key, ref->level + 1,
 					       node->bytenr,
 					       node->ref_mod * sgn,
-					       GFP_ATOMIC);
+					       sc, GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -772,7 +819,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			ret = add_direct_ref(fs_info, preftrees,
 					     ref->level + 1, ref->parent,
 					     node->bytenr, node->ref_mod * sgn,
-					     GFP_ATOMIC);
+					     sc, GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_EXTENT_DATA_REF_KEY: {
@@ -788,15 +835,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			 * Found a inum that doesn't match our known inum, we
 			 * know it's shared.
 			 */
-			if (inum && ref->objectid != inum) {
+			if (sc && sc->inum && ref->objectid != sc->inum) {
 				ret = BACKREF_FOUND_SHARED;
-				break;
+				goto out;
 			}
 
 			ret = add_indirect_ref(fs_info, preftrees, ref->root,
 					       &key, 0, node->bytenr,
 					       node->ref_mod * sgn,
-					       GFP_ATOMIC);
+					       sc, GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_DATA_REF_KEY: {
@@ -808,26 +855,35 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			ret = add_direct_ref(fs_info, preftrees, 0,
 					     ref->parent, node->bytenr,
 					     node->ref_mod * sgn,
-					     GFP_ATOMIC);
+					     sc, GFP_ATOMIC);
 			break;
 		}
 		default:
 			WARN_ON(1);
 		}
-		if (ret)
+		/*
+		 * We must ignore BACKREF_FOUND_SHARED until all delayed
+		 * refs have been checked.
+		 */
+		if (ret && (ret != BACKREF_FOUND_SHARED))
 			break;
 	}
+	if (!ret)
+		ret = extent_is_shared(sc);
+out:
 	spin_unlock(&head->lock);
 	return ret;
 }
 
 /*
  * add all inline backrefs for bytenr to the list
+ *
+ * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
  */
 static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 			   struct btrfs_path *path, u64 bytenr,
 			   int *info_level, struct preftrees *preftrees,
-			   u64 *total_refs, u64 inum)
+			   u64 *total_refs, struct share_check *sc)
 {
 	int ret = 0;
 	int slot;
@@ -884,7 +940,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 		case BTRFS_SHARED_BLOCK_REF_KEY:
 			ret = add_direct_ref(fs_info, preftrees,
 					     *info_level + 1, offset,
-					     bytenr, 1, GFP_NOFS);
+					     bytenr, 1, NULL, GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
 			struct btrfs_shared_data_ref *sdref;
@@ -894,13 +950,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 			count = btrfs_shared_data_ref_count(leaf, sdref);
 
 			ret = add_direct_ref(fs_info, preftrees, 0, offset,
-					     bytenr, count, GFP_NOFS);
+					     bytenr, count, sc, GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
 			ret = add_indirect_ref(fs_info, preftrees, offset,
 					       NULL, *info_level + 1,
-					       bytenr, 1, GFP_NOFS);
+					       bytenr, 1, NULL, GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
 			struct btrfs_extent_data_ref *dref;
@@ -914,7 +970,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 			key.type = BTRFS_EXTENT_DATA_KEY;
 			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
 
-			if (inum && key.objectid != inum) {
+			if (sc && sc->inum && key.objectid != sc->inum) {
 				ret = BACKREF_FOUND_SHARED;
 				break;
 			}
@@ -923,7 +979,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 
 			ret = add_indirect_ref(fs_info, preftrees, root,
 					       &key, 0, bytenr, count,
-					       GFP_NOFS);
+					       sc, GFP_NOFS);
 			break;
 		}
 		default:
@@ -939,11 +995,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
 
 /*
  * add all non-inline backrefs for bytenr to the list
+ *
+ * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
  */
 static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			  struct btrfs_path *path, u64 bytenr,
 			  int info_level, struct preftrees *preftrees,
-			  u64 inum)
+			  struct share_check *sc)
 {
 	struct btrfs_root *extent_root = fs_info->extent_root;
 	int ret;
@@ -976,7 +1034,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			/* SHARED DIRECT METADATA backref */
 			ret = add_direct_ref(fs_info, preftrees,
 					     info_level + 1, key.offset,
-					     bytenr, 1, GFP_NOFS);
+					     bytenr, 1, NULL, GFP_NOFS);
 			break;
 		case BTRFS_SHARED_DATA_REF_KEY: {
 			/* SHARED DIRECT FULL backref */
@@ -988,14 +1046,14 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			count = btrfs_shared_data_ref_count(leaf, sdref);
 			ret = add_direct_ref(fs_info, preftrees, 0,
 					     key.offset, bytenr, count,
-					     GFP_NOFS);
+					     sc, GFP_NOFS);
 			break;
 		}
 		case BTRFS_TREE_BLOCK_REF_KEY:
 			/* NORMAL INDIRECT METADATA backref */
 			ret = add_indirect_ref(fs_info, preftrees, key.offset,
 					       NULL, info_level + 1, bytenr,
-					       1, GFP_NOFS);
+					       1, NULL, GFP_NOFS);
 			break;
 		case BTRFS_EXTENT_DATA_REF_KEY: {
 			/* NORMAL INDIRECT DATA backref */
@@ -1011,7 +1069,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			key.type = BTRFS_EXTENT_DATA_KEY;
 			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
 
-			if (inum && key.objectid != inum) {
+			if (sc && sc->inum && key.objectid != sc->inum) {
 				ret = BACKREF_FOUND_SHARED;
 				break;
 			}
@@ -1019,7 +1077,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
 			root = btrfs_extent_data_ref_root(leaf, dref);
 			ret = add_indirect_ref(fs_info, preftrees, root,
 					       &key, 0, bytenr, count,
-					       GFP_NOFS);
+					       sc, GFP_NOFS);
 			break;
 		}
 		default:
@@ -1039,20 +1097,23 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
  * indirect refs to their parent bytenr.
  * When roots are found, they're added to the roots list
  *
- * NOTE: This can return values > 0
- *
  * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
  * much like trans == NULL case, the difference only lies in it will not
  * commit root.
  * The special case is for qgroup to search roots in commit_transaction().
  *
+ * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
+ * shared extent is detected.
+ *
+ * Otherwise this returns 0 for success and <0 for an error.
+ *
  * FIXME some caching might speed things up
  */
 static int find_parent_nodes(struct btrfs_trans_handle *trans,
 			     struct btrfs_fs_info *fs_info, u64 bytenr,
 			     u64 time_seq, struct ulist *refs,
 			     struct ulist *roots, const u64 *extent_item_pos,
-			     u64 root_objectid, u64 inum)
+			     struct share_check *sc)
 {
 	struct btrfs_key key;
 	struct btrfs_path *path;
@@ -1133,7 +1194,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 			}
 			spin_unlock(&delayed_refs->lock);
 			ret = add_delayed_refs(fs_info, head, time_seq,
-					       &preftrees, &total_refs, inum);
+					       &preftrees, &total_refs, sc);
 			mutex_unlock(&head->mutex);
 			if (ret)
 				goto out;
@@ -1155,11 +1216,11 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 		     key.type == BTRFS_METADATA_ITEM_KEY)) {
 			ret = add_inline_refs(fs_info, path, bytenr,
 					      &info_level, &preftrees,
-					      &total_refs, inum);
+					      &total_refs, sc);
 			if (ret)
 				goto out;
 			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
-					     &preftrees, inum);
+					     &preftrees, sc);
 			if (ret)
 				goto out;
 		}
@@ -1174,8 +1235,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
 
 	ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
-				    extent_item_pos, total_refs,
-				    root_objectid);
+				    extent_item_pos, total_refs, sc);
 	if (ret)
 		goto out;
 
@@ -1194,7 +1254,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
 		node = rb_next(&ref->rbnode);
 		WARN_ON(ref->count < 0);
 		if (roots && ref->count && ref->root_id && ref->parent == 0) {
-			if (root_objectid && ref->root_id != root_objectid) {
+			if (sc && sc->root_objectid &&
+			    ref->root_id != sc->root_objectid) {
 				ret = BACKREF_FOUND_SHARED;
 				goto out;
 			}
@@ -1298,7 +1359,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
 		return -ENOMEM;
 
 	ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
-				*leafs, NULL, extent_item_pos, 0, 0);
+				*leafs, NULL, extent_item_pos, NULL);
 	if (ret < 0 && ret != -ENOENT) {
 		free_leaf_list(*leafs);
 		return ret;
@@ -1341,7 +1402,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
 		ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
-					tmp, *roots, NULL, 0, 0);
+					tmp, *roots, NULL, NULL);
 		if (ret < 0 && ret != -ENOENT) {
 			ulist_free(tmp);
 			ulist_free(*roots);
@@ -1397,6 +1458,11 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
 	struct ulist_node *node;
 	struct seq_list elem = SEQ_LIST_INIT(elem);
 	int ret = 0;
+	struct share_check shared = {
+		.root_objectid = root->objectid,
+		.inum = inum,
+		.share_count = 0,
+	};
 
 	tmp = ulist_alloc(GFP_NOFS);
 	roots = ulist_alloc(GFP_NOFS);
@@ -1417,7 +1483,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
 		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
-					roots, NULL, root->objectid, inum);
+					roots, NULL, &shared);
 		if (ret == BACKREF_FOUND_SHARED) {
 			/* this is the only condition under which we return 1 */
 			ret = 1;
-- 
2.10.2

[PATCH v3 13/13] btrfs: clean up extraneous computations in add_delayed_refs

[Edmund Nadolski]

Repeating the same computation in multiple places is not
necessary.

Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/btrfs/backref.c | 30 +++++++++++++-----------------
 1 file changed, 13 insertions(+), 17 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 35ac0bd..e62704a 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -769,7 +769,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 	struct btrfs_key key;
 	struct btrfs_key tmp_op_key;
 	struct btrfs_key *op_key = NULL;
-	int sgn;
+	int count;
 	int ret = 0;
 
 	if (extent_op && extent_op->update_key) {
@@ -788,15 +788,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			WARN_ON(1);
 			continue;
 		case BTRFS_ADD_DELAYED_REF:
-			sgn = 1;
+			count = node->ref_mod;
 			break;
 		case BTRFS_DROP_DELAYED_REF:
-			sgn = -1;
+			count = node->ref_mod * -1;
 			break;
 		default:
 			BUG_ON(1);
 		}
-		*total_refs += (node->ref_mod * sgn);
+		*total_refs += count;
 		switch (node->type) {
 		case BTRFS_TREE_BLOCK_REF_KEY: {
 			/* NORMAL INDIRECT METADATA backref */
@@ -805,9 +805,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			ref = btrfs_delayed_node_to_tree_ref(node);
 			ret = add_indirect_ref(fs_info, preftrees, ref->root,
 					       &tmp_op_key, ref->level + 1,
-					       node->bytenr,
-					       node->ref_mod * sgn,
-					       sc, GFP_ATOMIC);
+					       node->bytenr, count, sc,
+					       GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -816,9 +815,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 
 			ref = btrfs_delayed_node_to_tree_ref(node);
 
-			ret = add_direct_ref(fs_info, preftrees,
-					     ref->level + 1, ref->parent,
-					     node->bytenr, node->ref_mod * sgn,
+			ret = add_direct_ref(fs_info, preftrees, ref->level + 1,
+					     ref->parent, node->bytenr, count,
 					     sc, GFP_ATOMIC);
 			break;
 		}
@@ -841,9 +839,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 			}
 
 			ret = add_indirect_ref(fs_info, preftrees, ref->root,
-					       &key, 0, node->bytenr,
-					       node->ref_mod * sgn,
-					       sc, GFP_ATOMIC);
+					       &key, 0, node->bytenr, count, sc,
+					       GFP_ATOMIC);
 			break;
 		}
 		case BTRFS_SHARED_DATA_REF_KEY: {
@@ -852,10 +849,9 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
 
 			ref = btrfs_delayed_node_to_data_ref(node);
 
-			ret = add_direct_ref(fs_info, preftrees, 0,
-					     ref->parent, node->bytenr,
-					     node->ref_mod * sgn,
-					     sc, GFP_ATOMIC);
+			ret = add_direct_ref(fs_info, preftrees, 0, ref->parent,
+					     node->bytenr, count, sc,
+					     GFP_ATOMIC);
 			break;
 		}
 		default:
-- 
2.10.2

Re: [PATCH v3 11/13] btrfs: add cond_resched() calls when resolving backrefs

[David Sterba]

On Wed, Jul 12, 2017 at 04:20:09PM -0600, Edmund Nadolski wrote:
> Since backref resolution is CPU-intensive, the cond_resched calls
> should help alleviate soft lockup occurences.
> 
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>

Reviewed-by: David Sterba <dsterba@suse.com>

Re: [PATCH v3 13/13] btrfs: clean up extraneous computations in add_delayed_refs

[David Sterba]

On Wed, Jul 12, 2017 at 04:20:11PM -0600, Edmund Nadolski wrote:
> Repeating the same computation in multiple places is not
> necessary.
> 
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>

Reviewed-by: David Sterba <dsterba@suse.com>

Re: [PATCH v3 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging

[David Sterba]

On Wed, Jul 12, 2017 at 04:20:08PM -0600, Edmund Nadolski wrote:
> From: Jeff Mahoney <jeffm@suse.com>
> 
> This patch adds a tracepoint event for prelim_ref insertion and
> merging.  For each, the ref being inserted or merged and the count
> of tree nodes is issued.
> 
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>

Reviewed-by: David Sterba <dsterba@suse.com>

I've chanbed "key=[%llu %u %llu]" -> "key=[%llu,%u,%llu]" and updated
the wiki.

Re: [PATCH v3 09/13] btrfs: add a node counter to each of the rbtrees

[David Sterba]

On Wed, Jul 12, 2017 at 04:20:07PM -0600, Edmund Nadolski wrote:
> From: Jeff Mahoney <jeffm@suse.com>
> 
> This patch adds counters to each of the rbtrees so that we can tell
> how large they are growing for a given workload.  These counters
> will be exported by tracepoints in the next patch.
> 
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>

Reviewed-by: David Sterba <dsterba@suse.com>

Re: [PATCH v3 00/13] use rbtrees for preliminary backrefs

[David Sterba]

On Wed, Jul 12, 2017 at 04:20:05PM -0600, Edmund Nadolski wrote:
> This patch series attempts to improve the performance of backref
> searches by changing the prelim_refs implementation to use
> rbtrees instead of lists.  This also aims to reduce the soft
> lockup occurences that can result when a backref search consumes
> too much cpu time.
> 
> Test runs of btrfs/130 show an improvement in the overall
> run time of the test (shown below in seconds) as a function of
> the number of extents:
> 
>     nr_extents:    256    512    640    1024     2048
>     ------------+-------+-----+-------+-------+------
>      unpatched:     20    186    375    2204    40419
>        patched:     12     93    203    1060    22007
> 
> (Note, the current default value for nr_extents in btrfs/130 is
> 4096, which takes a very long time to complete.)
> 
> Changes for v3:
> 
> Patch 08/13:
>  - Update changelog and comments for third rbtree.
>  - Fixed issue in resolve_indirect_refs() which prevented
>    module load when sanity checking was enabled.
> 
> Patch 10/13:
>  - Fix TP_printk_btrfs format string per coding standards.
> 
> Changes for v2:
> 
> Patch 06/13:
>  - Added changelog description.
> 
> Patch 07/13:
>  - Updated changelog description.
>  - Removed 'TODO' comment.
> 
> Patch 08/13:
>  - Added code for proper iteration of missing keys. This adds
>    a third rbtree (.indirect_missing_keys in struct preftrees)
>    plus the requisite code in add_prelim_ref(), add_missing_keys(),
>    resolve_indirect_refs(), and find_parent_nodes().
>  - Rename release_pref() to free_pref().
>  - Replace WARN() with BUG_ON().
>  - Remove 'TODO' comments and the unused 'merge_mode' enum.
> 
> The other patches have no functional changes. Some have diff
> context changes due to the above modifications.
> 
> Edmund Nadolski (6):
>   btrfs: btrfs_check_shared should manage its own transaction
>   btrfs: remove ref_tree implementation from backref.c
>   btrfs: convert prelimary reference tracking to use rbtrees
>   btrfs: add cond_resched() calls when resolving backrefs
>   btrfs: allow backref search checks for shared extents
>   btrfs: clean up extraneous computations in add_delayed_refs
> 
> Jeff Mahoney (7):
>   btrfs: struct-funcs, constify readers
>   btrfs: constify tracepoint arguments
>   btrfs: backref, constify some arguments
>   btrfs: backref, add unode_aux_to_inode_list helper
>   btrfs: backref, cleanup __ namespace abuse
>   btrfs: add a node counter to each of the rbtrees
>   btrfs: backref, add tracepoints for prelim_ref insertion and merging

FYI, the whole patchset is now queued for 4.14. It's been in for-next
for a long time and I haven't seen any problems related to it.

Re: [PATCH v3 08/13] btrfs: convert prelimary reference tracking to use rbtrees

[Liu Bo]

On Wed, Jul 12, 2017 at 04:20:06PM -0600, Edmund Nadolski wrote:
> It's been known for a while that the use of multiple lists
> that are periodically merged was an algorithmic problem within
> btrfs.  There are several workloads that don't complete in any
> reasonable amount of time (e.g. btrfs/130) and others that cause
> soft lockups.
> 
> The solution is to use a set of rbtrees that do insertion merging
> for both indirect and direct refs, with the former converting
> refs into the latter.  The result is a btrfs/130 workload that
> used to take several hours now takes about half of that. This
> runtime still isn't acceptable and a future patch will address that
> by moving the rbtrees higher in the stack so the lookups can be
> shared across multiple calls to find_parent_nodes.
>


Reviewed-by: Liu Bo <bo.li.liu@oracle.com>

Thanks,

-liubo
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
> ---
>  fs/btrfs/backref.c | 441 ++++++++++++++++++++++++++++++++++-------------------
>  1 file changed, 284 insertions(+), 157 deletions(-)
> 
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index 6cac5ab..1edb107 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -26,11 +26,6 @@
>  #include "delayed-ref.h"
>  #include "locking.h"
>  
> -enum merge_mode {
> -	MERGE_IDENTICAL_KEYS = 1,
> -	MERGE_IDENTICAL_PARENTS,
> -};
> -
>  /* Just an arbitrary number so we can be sure this happened */
>  #define BACKREF_FOUND_SHARED 6
>  
> @@ -129,7 +124,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
>   * this structure records all encountered refs on the way up to the root
>   */
>  struct prelim_ref {
> -	struct list_head list;
> +	struct rb_node rbnode;
>  	u64 root_id;
>  	struct btrfs_key key_for_search;
>  	int level;
> @@ -139,6 +134,18 @@ struct prelim_ref {
>  	u64 wanted_disk_byte;
>  };
>  
> +struct preftree {
> +	struct rb_root root;
> +};
> +
> +#define PREFTREE_INIT	{ .root = RB_ROOT }
> +
> +struct preftrees {
> +	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
> +	struct preftree indirect;  /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
> +	struct preftree indirect_missing_keys;
> +};
> +
>  static struct kmem_cache *btrfs_prelim_ref_cache;
>  
>  int __init btrfs_prelim_ref_init(void)
> @@ -158,6 +165,108 @@ void btrfs_prelim_ref_exit(void)
>  	kmem_cache_destroy(btrfs_prelim_ref_cache);
>  }
>  
> +static void free_pref(struct prelim_ref *ref)
> +{
> +	kmem_cache_free(btrfs_prelim_ref_cache, ref);
> +}
> +
> +/*
> + * Return 0 when both refs are for the same block (and can be merged).
> + * A -1 return indicates ref1 is a 'lower' block than ref2, while 1
> + * indicates a 'higher' block.
> + */
> +static int prelim_ref_compare(struct prelim_ref *ref1,
> +			      struct prelim_ref *ref2)
> +{
> +	if (ref1->level < ref2->level)
> +		return -1;
> +	if (ref1->level > ref2->level)
> +		return 1;
> +	if (ref1->root_id < ref2->root_id)
> +		return -1;
> +	if (ref1->root_id > ref2->root_id)
> +		return 1;
> +	if (ref1->key_for_search.type < ref2->key_for_search.type)
> +		return -1;
> +	if (ref1->key_for_search.type > ref2->key_for_search.type)
> +		return 1;
> +	if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
> +		return -1;
> +	if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
> +		return 1;
> +	if (ref1->key_for_search.offset < ref2->key_for_search.offset)
> +		return -1;
> +	if (ref1->key_for_search.offset > ref2->key_for_search.offset)
> +		return 1;
> +	if (ref1->parent < ref2->parent)
> +		return -1;
> +	if (ref1->parent > ref2->parent)
> +		return 1;
> +
> +	return 0;
> +}
> +
> +/*
> + * Add @newref to the @root rbtree, merging identical refs.
> + *
> + * Callers should assumed that newref has been freed after calling.
> + */
> +static void prelim_ref_insert(struct preftree *preftree,
> +			      struct prelim_ref *newref)
> +{
> +	struct rb_root *root;
> +	struct rb_node **p;
> +	struct rb_node *parent = NULL;
> +	struct prelim_ref *ref;
> +	int result;
> +
> +	root = &preftree->root;
> +	p = &root->rb_node;
> +
> +	while (*p) {
> +		parent = *p;
> +		ref = rb_entry(parent, struct prelim_ref, rbnode);
> +		result = prelim_ref_compare(ref, newref);
> +		if (result < 0) {
> +			p = &(*p)->rb_left;
> +		} else if (result > 0) {
> +			p = &(*p)->rb_right;
> +		} else {
> +			/* Identical refs, merge them and free @newref */
> +			struct extent_inode_elem *eie = ref->inode_list;
> +
> +			while (eie && eie->next)
> +				eie = eie->next;
> +
> +			if (!eie)
> +				ref->inode_list = newref->inode_list;
> +			else
> +				eie->next = newref->inode_list;
> +			ref->count += newref->count;
> +			free_pref(newref);
> +			return;
> +		}
> +	}
> +
> +	rb_link_node(&newref->rbnode, parent, p);
> +	rb_insert_color(&newref->rbnode, root);
> +}
> +
> +/*
> + * Release the entire tree.  We don't care about internal consistency so
> + * just free everything and then reset the tree root.
> + */
> +static void prelim_release(struct preftree *preftree)
> +{
> +	struct prelim_ref *ref, *next_ref;
> +
> +	rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root,
> +					     rbnode)
> +		free_pref(ref);
> +
> +	preftree->root = RB_ROOT;
> +}
> +
>  /*
>   * the rules for all callers of this function are:
>   * - obtaining the parent is the goal
> @@ -196,7 +305,7 @@ void btrfs_prelim_ref_exit(void)
>   * additional information that's available but not required to find the parent
>   * block might help in merging entries to gain some speed.
>   */
> -static int add_prelim_ref(struct list_head *head, u64 root_id,
> +static int add_prelim_ref(struct preftree *preftree, u64 root_id,
>  			  const struct btrfs_key *key, int level, u64 parent,
>  			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
>  {
> @@ -243,11 +352,31 @@ static int add_prelim_ref(struct list_head *head, u64 root_id,
>  	ref->count = count;
>  	ref->parent = parent;
>  	ref->wanted_disk_byte = wanted_disk_byte;
> -	list_add_tail(&ref->list, head);
> +	prelim_ref_insert(preftree, ref);
>  
>  	return 0;
>  }
>  
> +/* direct refs use root == 0, key == NULL */
> +static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
> +			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +{
> +	return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
> +			      wanted_disk_byte, count, gfp_mask);
> +}
> +
> +/* indirect refs use parent == 0 */
> +static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
> +			    const struct btrfs_key *key, int level,
> +			    u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +{
> +	struct preftree *tree = &preftrees->indirect;
> +	if (!key)
> +		tree = &preftrees->indirect_missing_keys;
> +	return add_prelim_ref(tree, root_id, key, level, 0,
> +			      wanted_disk_byte, count, gfp_mask);
> +}
> +
>  static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
>  			   struct ulist *parents, struct prelim_ref *ref,
>  			   int level, u64 time_seq, const u64 *extent_item_pos,
> @@ -429,38 +558,63 @@ unode_aux_to_inode_list(struct ulist_node *node)
>  }
>  
>  /*
> - * resolve all indirect backrefs from the list
> + * We maintain three seperate rbtrees: one for direct refs, one for
> + * indirect refs which have a key, and one for indirect refs which do not
> + * have a key. Each tree does merge on insertion.
> + *
> + * Once all of the references are located, we iterate over the tree of
> + * indirect refs with missing keys. An appropriate key is located and
> + * the ref is moved onto the tree for indirect refs. After all missing
> + * keys are thus located, we iterate over the indirect ref tree, resolve
> + * each reference, and then insert the resolved reference onto the
> + * direct tree (merging there too).
> + *
> + * New backrefs (i.e., for parent nodes) are added to the appropriate
> + * rbtree as they are encountered. The new backrefs are subsequently
> + * resolved as above.
>   */
>  static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  				 struct btrfs_path *path, u64 time_seq,
> -				 struct list_head *head,
> +				 struct preftrees *preftrees,
>  				 const u64 *extent_item_pos, u64 total_refs,
>  				 u64 root_objectid)
>  {
>  	int err;
>  	int ret = 0;
> -	struct prelim_ref *ref;
> -	struct prelim_ref *ref_safe;
> -	struct prelim_ref *new_ref;
>  	struct ulist *parents;
>  	struct ulist_node *node;
>  	struct ulist_iterator uiter;
> +	struct rb_node *rnode;
>  
>  	parents = ulist_alloc(GFP_NOFS);
>  	if (!parents)
>  		return -ENOMEM;
>  
>  	/*
> -	 * _safe allows us to insert directly after the current item without
> -	 * iterating over the newly inserted items.
> -	 * we're also allowed to re-assign ref during iteration.
> +	 * We could trade memory usage for performance here by iterating
> +	 * the tree, allocating new refs for each insertion, and then
> +	 * freeing the entire indirect tree when we're done.  In some test
> +	 * cases, the tree can grow quite large (~200k objects).
>  	 */
> -	list_for_each_entry_safe(ref, ref_safe, head, list) {
> -		if (ref->parent)	/* already direct */
> -			continue;
> -		if (ref->count == 0)
> +	while ((rnode = rb_first(&preftrees->indirect.root))) {
> +		struct prelim_ref *ref;
> +
> +		ref = rb_entry(rnode, struct prelim_ref, rbnode);
> +		if (WARN(ref->parent,
> +			 "BUG: direct ref found in indirect tree")) {
> +			ret = -EINVAL;
> +			goto out;
> +		}
> +
> +		rb_erase(&ref->rbnode, &preftrees->indirect.root);
> +
> +		if (ref->count == 0) {
> +			free_pref(ref);
>  			continue;
> +		}
> +
>  		if (root_objectid && ref->root_id != root_objectid) {
> +			free_pref(ref);
>  			ret = BACKREF_FOUND_SHARED;
>  			goto out;
>  		}
> @@ -472,8 +626,10 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  		 * and return directly.
>  		 */
>  		if (err == -ENOENT) {
> +			prelim_ref_insert(&preftrees->direct, ref);
>  			continue;
>  		} else if (err) {
> +			free_pref(ref);
>  			ret = err;
>  			goto out;
>  		}
> @@ -484,19 +640,26 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  		ref->parent = node ? node->val : 0;
>  		ref->inode_list = unode_aux_to_inode_list(node);
>  
> -		/* additional parents require new refs being added here */
> +		/* Add a prelim_ref(s) for any other parent(s). */
>  		while ((node = ulist_next(parents, &uiter))) {
> +			struct prelim_ref *new_ref;
> +
>  			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
>  						   GFP_NOFS);
>  			if (!new_ref) {
> +				free_pref(ref);
>  				ret = -ENOMEM;
>  				goto out;
>  			}
>  			memcpy(new_ref, ref, sizeof(*ref));
>  			new_ref->parent = node->val;
>  			new_ref->inode_list = unode_aux_to_inode_list(node);
> -			list_add(&new_ref->list, &ref->list);
> +			prelim_ref_insert(&preftrees->direct, new_ref);
>  		}
> +
> +		/* Now it's a direct ref, put it in the the direct tree */
> +		prelim_ref_insert(&preftrees->direct, ref);
> +
>  		ulist_reinit(parents);
>  	}
>  out:
> @@ -504,44 +667,31 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  	return ret;
>  }
>  
> -static inline int ref_for_same_block(struct prelim_ref *ref1,
> -				     struct prelim_ref *ref2)
> -{
> -	if (ref1->level != ref2->level)
> -		return 0;
> -	if (ref1->root_id != ref2->root_id)
> -		return 0;
> -	if (ref1->key_for_search.type != ref2->key_for_search.type)
> -		return 0;
> -	if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
> -		return 0;
> -	if (ref1->key_for_search.offset != ref2->key_for_search.offset)
> -		return 0;
> -	if (ref1->parent != ref2->parent)
> -		return 0;
> -
> -	return 1;
> -}
> -
>  /*
>   * read tree blocks and add keys where required.
>   */
>  static int add_missing_keys(struct btrfs_fs_info *fs_info,
> -			    struct list_head *head)
> +			    struct preftrees *preftrees)
>  {
>  	struct prelim_ref *ref;
>  	struct extent_buffer *eb;
> +	struct preftree *tree = &preftrees->indirect_missing_keys;
> +	struct rb_node *node;
>  
> -	list_for_each_entry(ref, head, list) {
> -		if (ref->parent)
> -			continue;
> -		if (ref->key_for_search.type)
> -			continue;
> +	while ((node = rb_first(&tree->root))) {
> +		ref = rb_entry(node, struct prelim_ref, rbnode);
> +		rb_erase(node, &tree->root);
> +
> +		BUG_ON(ref->parent);	/* should not be a direct ref */
> +		BUG_ON(ref->key_for_search.type);
>  		BUG_ON(!ref->wanted_disk_byte);
> +
>  		eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
>  		if (IS_ERR(eb)) {
> +			free_pref(ref);
>  			return PTR_ERR(eb);
>  		} else if (!extent_buffer_uptodate(eb)) {
> +			free_pref(ref);
>  			free_extent_buffer(eb);
>  			return -EIO;
>  		}
> @@ -552,73 +702,31 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
>  			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
>  		btrfs_tree_read_unlock(eb);
>  		free_extent_buffer(eb);
> +		prelim_ref_insert(&preftrees->indirect, ref);
>  	}
>  	return 0;
>  }
>  
>  /*
> - * merge backrefs and adjust counts accordingly
> - *
> - *    FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref
> - *           then we can merge more here. Additionally, we could even add a key
> - *           range for the blocks we looked into to merge even more (-> replace
> - *           unresolved refs by those having a parent).
> - */
> -static void merge_refs(struct list_head *head, enum merge_mode mode)
> -{
> -	struct prelim_ref *pos1;
> -
> -	list_for_each_entry(pos1, head, list) {
> -		struct prelim_ref *pos2 = pos1, *tmp;
> -
> -		list_for_each_entry_safe_continue(pos2, tmp, head, list) {
> -			struct prelim_ref *ref1 = pos1, *ref2 = pos2;
> -			struct extent_inode_elem *eie;
> -
> -			if (!ref_for_same_block(ref1, ref2))
> -				continue;
> -			if (mode == MERGE_IDENTICAL_KEYS) {
> -				if (!ref1->parent && ref2->parent)
> -					swap(ref1, ref2);
> -			} else {
> -				if (ref1->parent != ref2->parent)
> -					continue;
> -			}
> -
> -			eie = ref1->inode_list;
> -			while (eie && eie->next)
> -				eie = eie->next;
> -			if (eie)
> -				eie->next = ref2->inode_list;
> -			else
> -				ref1->inode_list = ref2->inode_list;
> -			ref1->count += ref2->count;
> -
> -			list_del(&ref2->list);
> -			kmem_cache_free(btrfs_prelim_ref_cache, ref2);
> -			cond_resched();
> -		}
> -
> -	}
> -}
> -
> -/*
>   * add all currently queued delayed refs from this head whose seq nr is
>   * smaller or equal that seq to the list
>   */
>  static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
> -			    struct list_head *prefs, u64 *total_refs,
> +			    struct preftrees *preftrees, u64 *total_refs,
>  			    u64 inum)
>  {
>  	struct btrfs_delayed_ref_node *node;
>  	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
>  	struct btrfs_key key;
> -	struct btrfs_key op_key = {0};
> +	struct btrfs_key tmp_op_key;
> +	struct btrfs_key *op_key = NULL;
>  	int sgn;
>  	int ret = 0;
>  
> -	if (extent_op && extent_op->update_key)
> -		btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
> +	if (extent_op && extent_op->update_key) {
> +		btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key);
> +		op_key = &tmp_op_key;
> +	}
>  
>  	spin_lock(&head->lock);
>  	list_for_each_entry(node, &head->ref_list, list) {
> @@ -642,24 +750,30 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
>  		*total_refs += (node->ref_mod * sgn);
>  		switch (node->type) {
>  		case BTRFS_TREE_BLOCK_REF_KEY: {
> +			/* NORMAL INDIRECT METADATA backref */
>  			struct btrfs_delayed_tree_ref *ref;
>  
>  			ref = btrfs_delayed_node_to_tree_ref(node);
> -			ret = add_prelim_ref(prefs, ref->root, &op_key,
> -					     ref->level + 1, 0, node->bytenr,
> -					     node->ref_mod * sgn, GFP_ATOMIC);
> +			ret = add_indirect_ref(preftrees, ref->root, &tmp_op_key,
> +					       ref->level + 1, node->bytenr,
> +					       node->ref_mod * sgn,
> +					       GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_SHARED_BLOCK_REF_KEY: {
> +			/* SHARED DIRECT METADATA backref */
>  			struct btrfs_delayed_tree_ref *ref;
>  
>  			ref = btrfs_delayed_node_to_tree_ref(node);
> -			ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1,
> +
> +			ret = add_direct_ref(preftrees, ref->level + 1,
>  					     ref->parent, node->bytenr,
> -					     node->ref_mod * sgn, GFP_ATOMIC);
> +					     node->ref_mod * sgn,
> +					     GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
> +			/* NORMAL INDIRECT DATA backref */
>  			struct btrfs_delayed_data_ref *ref;
>  			ref = btrfs_delayed_node_to_data_ref(node);
>  
> @@ -676,17 +790,21 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
>  				break;
>  			}
>  
> -			ret = add_prelim_ref(prefs, ref->root, &key, 0, 0,
> -					     node->bytenr, node->ref_mod * sgn,
> -					     GFP_ATOMIC);
> +			ret = add_indirect_ref(preftrees, ref->root, &key, 0,
> +					       node->bytenr,
> +					       node->ref_mod * sgn,
> +					       GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_SHARED_DATA_REF_KEY: {
> +			/* SHARED DIRECT FULL backref */
>  			struct btrfs_delayed_data_ref *ref;
>  
>  			ref = btrfs_delayed_node_to_data_ref(node);
> -			ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent,
> -					     node->bytenr, node->ref_mod * sgn,
> +
> +			ret = add_direct_ref(preftrees, 0, ref->parent,
> +					     node->bytenr,
> +					     node->ref_mod * sgn,
>  					     GFP_ATOMIC);
>  			break;
>  		}
> @@ -704,7 +822,7 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
>   * add all inline backrefs for bytenr to the list
>   */
>  static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
> -			   int *info_level, struct list_head *prefs,
> +			   int *info_level, struct preftrees *preftrees,
>  			   u64 *total_refs, u64 inum)
>  {
>  	int ret = 0;
> @@ -760,8 +878,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>  
>  		switch (type) {
>  		case BTRFS_SHARED_BLOCK_REF_KEY:
> -			ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1,
> -					     offset, bytenr, 1, GFP_NOFS);
> +			ret = add_direct_ref(preftrees, *info_level + 1, offset,
> +					     bytenr, 1, GFP_NOFS);
>  			break;
>  		case BTRFS_SHARED_DATA_REF_KEY: {
>  			struct btrfs_shared_data_ref *sdref;
> @@ -769,14 +887,15 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>  
>  			sdref = (struct btrfs_shared_data_ref *)(iref + 1);
>  			count = btrfs_shared_data_ref_count(leaf, sdref);
> -			ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
> +
> +			ret = add_direct_ref(preftrees, 0, offset,
>  					     bytenr, count, GFP_NOFS);
>  			break;
>  		}
>  		case BTRFS_TREE_BLOCK_REF_KEY:
> -			ret = add_prelim_ref(prefs, offset, NULL,
> -					     *info_level + 1, 0,
> -					     bytenr, 1, GFP_NOFS);
> +			ret = add_indirect_ref(preftrees, offset, NULL,
> +					       *info_level + 1, bytenr, 1,
> +					       GFP_NOFS);
>  			break;
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
>  			struct btrfs_extent_data_ref *dref;
> @@ -796,8 +915,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>  			}
>  
>  			root = btrfs_extent_data_ref_root(leaf, dref);
> -			ret = add_prelim_ref(prefs, root, &key, 0, 0,
> -					     bytenr, count, GFP_NOFS);
> +
> +			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
> +					       count, GFP_NOFS);
>  			break;
>  		}
>  		default:
> @@ -816,7 +936,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>   */
>  static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			  struct btrfs_path *path, u64 bytenr,
> -			  int info_level, struct list_head *prefs, u64 inum)
> +			  int info_level, struct preftrees *preftrees,
> +			  u64 inum)
>  {
>  	struct btrfs_root *extent_root = fs_info->extent_root;
>  	int ret;
> @@ -846,26 +967,31 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  
>  		switch (key.type) {
>  		case BTRFS_SHARED_BLOCK_REF_KEY:
> -			ret = add_prelim_ref(prefs, 0, NULL, info_level + 1,
> -					     key.offset, bytenr, 1, GFP_NOFS);
> +			/* SHARED DIRECT METADATA backref */
> +			ret = add_direct_ref(preftrees, info_level + 1,
> +					     key.offset, bytenr, 1,
> +					     GFP_NOFS);
>  			break;
>  		case BTRFS_SHARED_DATA_REF_KEY: {
> +			/* SHARED DIRECT FULL backref */
>  			struct btrfs_shared_data_ref *sdref;
>  			int count;
>  
>  			sdref = btrfs_item_ptr(leaf, slot,
>  					      struct btrfs_shared_data_ref);
>  			count = btrfs_shared_data_ref_count(leaf, sdref);
> -			ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
> -					     bytenr, count, GFP_NOFS);
> +			ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
> +					     count, GFP_NOFS);
>  			break;
>  		}
>  		case BTRFS_TREE_BLOCK_REF_KEY:
> -			ret = add_prelim_ref(prefs, key.offset, NULL,
> -					     info_level + 1, 0,
> -					     bytenr, 1, GFP_NOFS);
> +			/* NORMAL INDIRECT METADATA backref */
> +			ret = add_indirect_ref(preftrees, key.offset, NULL,
> +					       info_level + 1, bytenr, 1,
> +					       GFP_NOFS);
>  			break;
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
> +			/* NORMAL INDIRECT DATA backref */
>  			struct btrfs_extent_data_ref *dref;
>  			int count;
>  			u64 root;
> @@ -884,8 +1010,8 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			}
>  
>  			root = btrfs_extent_data_ref_root(leaf, dref);
> -			ret = add_prelim_ref(prefs, root, &key, 0, 0,
> -					     bytenr, count, GFP_NOFS);
> +			ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
> +					       count, GFP_NOFS);
>  			break;
>  		}
>  		default:
> @@ -926,14 +1052,16 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  	struct btrfs_delayed_ref_head *head;
>  	int info_level = 0;
>  	int ret;
> -	struct list_head prefs_delayed;
> -	struct list_head prefs;
>  	struct prelim_ref *ref;
> +	struct rb_node *node;
>  	struct extent_inode_elem *eie = NULL;
> +	/* total of both direct AND indirect refs! */
>  	u64 total_refs = 0;
> -
> -	INIT_LIST_HEAD(&prefs);
> -	INIT_LIST_HEAD(&prefs_delayed);
> +	struct preftrees preftrees = {
> +		.direct = PREFTREE_INIT,
> +		.indirect = PREFTREE_INIT,
> +		.indirect_missing_keys = PREFTREE_INIT
> +	};
>  
>  	key.objectid = bytenr;
>  	key.offset = (u64)-1;
> @@ -996,9 +1124,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  				goto again;
>  			}
>  			spin_unlock(&delayed_refs->lock);
> -			ret = add_delayed_refs(head, time_seq,
> -					       &prefs_delayed, &total_refs,
> -					       inum);
> +			ret = add_delayed_refs(head, time_seq, &preftrees,
> +					       &total_refs, inum);
>  			mutex_unlock(&head->mutex);
>  			if (ret)
>  				goto out;
> @@ -1019,35 +1146,43 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
>  		     key.type == BTRFS_METADATA_ITEM_KEY)) {
>  			ret = add_inline_refs(path, bytenr, &info_level,
> -					      &prefs, &total_refs, inum);
> +					      &preftrees, &total_refs, inum);
>  			if (ret)
>  				goto out;
>  			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
> -					     &prefs, inum);
> +					     &preftrees, inum);
>  			if (ret)
>  				goto out;
>  		}
>  	}
> -	btrfs_release_path(path);
>  
> -	list_splice_init(&prefs_delayed, &prefs);
> +	btrfs_release_path(path);
>  
> -	ret = add_missing_keys(fs_info, &prefs);
> +	ret = add_missing_keys(fs_info, &preftrees);
>  	if (ret)
>  		goto out;
>  
> -	merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
> +	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
>  
> -	ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs,
> +	ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
>  				    extent_item_pos, total_refs,
>  				    root_objectid);
>  	if (ret)
>  		goto out;
>  
> -	merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
> +	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root));
>  
> -	while (!list_empty(&prefs)) {
> -		ref = list_first_entry(&prefs, struct prelim_ref, list);
> +	/*
> +	 * This walks the tree of merged and resolved refs. Tree blocks are
> +	 * read in as needed. Unique entries are added to the ulist, and
> +	 * the list of found roots is updated.
> +	 *
> +	 * We release the entire tree in one go before returning.
> +	 */
> +	node = rb_first(&preftrees.direct.root);
> +	while (node) {
> +		ref = rb_entry(node, struct prelim_ref, rbnode);
> +		node = rb_next(&ref->rbnode);
>  		WARN_ON(ref->count < 0);
>  		if (roots && ref->count && ref->root_id && ref->parent == 0) {
>  			if (root_objectid && ref->root_id != root_objectid) {
> @@ -1101,23 +1236,15 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  			}
>  			eie = NULL;
>  		}
> -		list_del(&ref->list);
> -		kmem_cache_free(btrfs_prelim_ref_cache, ref);
>  	}
>  
>  out:
>  	btrfs_free_path(path);
> -	while (!list_empty(&prefs)) {
> -		ref = list_first_entry(&prefs, struct prelim_ref, list);
> -		list_del(&ref->list);
> -		kmem_cache_free(btrfs_prelim_ref_cache, ref);
> -	}
> -	while (!list_empty(&prefs_delayed)) {
> -		ref = list_first_entry(&prefs_delayed, struct prelim_ref,
> -				       list);
> -		list_del(&ref->list);
> -		kmem_cache_free(btrfs_prelim_ref_cache, ref);
> -	}
> +
> +	prelim_release(&preftrees.direct);
> +	prelim_release(&preftrees.indirect);
> +	prelim_release(&preftrees.indirect_missing_keys);
> +
>  	if (ret < 0)
>  		free_inode_elem_list(eie);
>  	return ret;
> -- 
> 2.10.2
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v3 12/13] btrfs: allow backref search checks for shared extents

[Liu Bo]

On Wed, Jul 12, 2017 at 04:20:10PM -0600, Edmund Nadolski wrote:
> When called with a struct share_check, find_parent_nodes()
> will detect a shared extent and immediately return with
> BACKREF_SHARED_FOUND.
> 

Reviewed-by: Liu Bo <bo.li.liu@oracle.com>

Thanks,

-liubo
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
> ---
>  fs/btrfs/backref.c | 164 +++++++++++++++++++++++++++++++++++++----------------
>  1 file changed, 115 insertions(+), 49 deletions(-)
> 
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index c1882e5..35ac0bd 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -135,6 +135,25 @@ struct preftrees {
>  	struct preftree indirect_missing_keys;
>  };
>  
> +/*
> + * Checks for a shared extent during backref search.
> + *
> + * The share_count tracks prelim_refs (direct and indirect) having a
> + * ref->count >0:
> + *  - incremented when a ref->count transitions to >0
> + *  - decremented when a ref->count transitions to <1
> + */
> +struct share_check {
> +	u64 root_objectid;
> +	u64 inum;
> +	int share_count;
> +};
> +
> +static inline int extent_is_shared(struct share_check *sc)
> +{
> +	return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;
> +}
> +
>  static struct kmem_cache *btrfs_prelim_ref_cache;
>  
>  int __init btrfs_prelim_ref_init(void)
> @@ -195,14 +214,26 @@ static int prelim_ref_compare(struct prelim_ref *ref1,
>  	return 0;
>  }
>  
> +void update_share_count(struct share_check *sc, int oldcount, int newcount)
> +{
> +	if ((!sc) || (oldcount == 0 && newcount < 1))
> +		return;
> +
> +	if (oldcount > 0 && newcount < 1)
> +		sc->share_count--;
> +	else if (oldcount < 1 && newcount > 0)
> +		sc->share_count++;
> +}
> +
>  /*
>   * Add @newref to the @root rbtree, merging identical refs.
>   *
> - * Callers should assumed that newref has been freed after calling.
> + * Callers should assume that newref has been freed after calling.
>   */
>  static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
>  			      struct preftree *preftree,
> -			      struct prelim_ref *newref)
> +			      struct prelim_ref *newref,
> +			      struct share_check *sc)
>  {
>  	struct rb_root *root;
>  	struct rb_node **p;
> @@ -234,12 +265,20 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
>  				eie->next = newref->inode_list;
>  			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
>  						     preftree->count);
> +			/*
> +			 * A delayed ref can have newref->count < 0.
> +			 * The ref->count is updated to follow any
> +			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
> +			 */
> +			update_share_count(sc, ref->count,
> +					   ref->count + newref->count);
>  			ref->count += newref->count;
>  			free_pref(newref);
>  			return;
>  		}
>  	}
>  
> +	update_share_count(sc, 0, newref->count);
>  	preftree->count++;
>  	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
>  	rb_link_node(&newref->rbnode, parent, p);
> @@ -303,7 +342,8 @@ static void prelim_release(struct preftree *preftree)
>  static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
>  			  struct preftree *preftree, u64 root_id,
>  			  const struct btrfs_key *key, int level, u64 parent,
> -			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +			  u64 wanted_disk_byte, int count,
> +			  struct share_check *sc, gfp_t gfp_mask)
>  {
>  	struct prelim_ref *ref;
>  
> @@ -348,31 +388,32 @@ static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
>  	ref->count = count;
>  	ref->parent = parent;
>  	ref->wanted_disk_byte = wanted_disk_byte;
> -	prelim_ref_insert(fs_info, preftree, ref);
> -
> -	return 0;
> +	prelim_ref_insert(fs_info, preftree, ref, sc);
> +	return extent_is_shared(sc);
>  }
>  
>  /* direct refs use root == 0, key == NULL */
>  static int add_direct_ref(const struct btrfs_fs_info *fs_info,
>  			  struct preftrees *preftrees, int level, u64 parent,
> -			  u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +			  u64 wanted_disk_byte, int count,
> +			  struct share_check *sc, gfp_t gfp_mask)
>  {
>  	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
> -			      parent, wanted_disk_byte, count, gfp_mask);
> +			      parent, wanted_disk_byte, count, sc, gfp_mask);
>  }
>  
>  /* indirect refs use parent == 0 */
>  static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
>  			    struct preftrees *preftrees, u64 root_id,
>  			    const struct btrfs_key *key, int level,
> -			    u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +			    u64 wanted_disk_byte, int count,
> +			    struct share_check *sc, gfp_t gfp_mask)
>  {
>  	struct preftree *tree = &preftrees->indirect;
>  	if (!key)
>  		tree = &preftrees->indirect_missing_keys;
>  	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
> -			      wanted_disk_byte, count, gfp_mask);
> +			      wanted_disk_byte, count, sc, gfp_mask);
>  }
>  
>  static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
> @@ -575,7 +616,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  				 struct btrfs_path *path, u64 time_seq,
>  				 struct preftrees *preftrees,
>  				 const u64 *extent_item_pos, u64 total_refs,
> -				 u64 root_objectid)
> +				 struct share_check *sc)
>  {
>  	int err;
>  	int ret = 0;
> @@ -612,7 +653,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  			continue;
>  		}
>  
> -		if (root_objectid && ref->root_id != root_objectid) {
> +		if (sc && sc->root_objectid &&
> +		    ref->root_id != sc->root_objectid) {
>  			free_pref(ref);
>  			ret = BACKREF_FOUND_SHARED;
>  			goto out;
> @@ -625,7 +667,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  		 * and return directly.
>  		 */
>  		if (err == -ENOENT) {
> -			prelim_ref_insert(fs_info, &preftrees->direct, ref);
> +			prelim_ref_insert(fs_info, &preftrees->direct, ref,
> +					  NULL);
>  			continue;
>  		} else if (err) {
>  			free_pref(ref);
> @@ -653,11 +696,15 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>  			memcpy(new_ref, ref, sizeof(*ref));
>  			new_ref->parent = node->val;
>  			new_ref->inode_list = unode_aux_to_inode_list(node);
> -			prelim_ref_insert(fs_info, &preftrees->direct, new_ref);
> +			prelim_ref_insert(fs_info, &preftrees->direct,
> +					  new_ref, NULL);
>  		}
>  
> -		/* Now it's a direct ref, put it in the the direct tree */
> -		prelim_ref_insert(fs_info, &preftrees->direct, ref);
> +		/*
> +		 * Now it's a direct ref, put it in the the direct tree. We must
> +		 * do this last because the ref could be merged/freed here.
> +		 */
> +		prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL);
>  
>  		ulist_reinit(parents);
>  		cond_resched();
> @@ -702,7 +749,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
>  			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
>  		btrfs_tree_read_unlock(eb);
>  		free_extent_buffer(eb);
> -		prelim_ref_insert(fs_info, &preftrees->indirect, ref);
> +		prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);
>  		cond_resched();
>  	}
>  	return 0;
> @@ -715,7 +762,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
>  static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
>  			    struct btrfs_delayed_ref_head *head, u64 seq,
>  			    struct preftrees *preftrees, u64 *total_refs,
> -			    u64 inum)
> +			    struct share_check *sc)
>  {
>  	struct btrfs_delayed_ref_node *node;
>  	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
> @@ -760,7 +807,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
>  					       &tmp_op_key, ref->level + 1,
>  					       node->bytenr,
>  					       node->ref_mod * sgn,
> -					       GFP_ATOMIC);
> +					       sc, GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_SHARED_BLOCK_REF_KEY: {
> @@ -772,7 +819,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
>  			ret = add_direct_ref(fs_info, preftrees,
>  					     ref->level + 1, ref->parent,
>  					     node->bytenr, node->ref_mod * sgn,
> -					     GFP_ATOMIC);
> +					     sc, GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
> @@ -788,15 +835,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
>  			 * Found a inum that doesn't match our known inum, we
>  			 * know it's shared.
>  			 */
> -			if (inum && ref->objectid != inum) {
> +			if (sc && sc->inum && ref->objectid != sc->inum) {
>  				ret = BACKREF_FOUND_SHARED;
> -				break;
> +				goto out;
>  			}
>  
>  			ret = add_indirect_ref(fs_info, preftrees, ref->root,
>  					       &key, 0, node->bytenr,
>  					       node->ref_mod * sgn,
> -					       GFP_ATOMIC);
> +					       sc, GFP_ATOMIC);
>  			break;
>  		}
>  		case BTRFS_SHARED_DATA_REF_KEY: {
> @@ -808,26 +855,35 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
>  			ret = add_direct_ref(fs_info, preftrees, 0,
>  					     ref->parent, node->bytenr,
>  					     node->ref_mod * sgn,
> -					     GFP_ATOMIC);
> +					     sc, GFP_ATOMIC);
>  			break;
>  		}
>  		default:
>  			WARN_ON(1);
>  		}
> -		if (ret)
> +		/*
> +		 * We must ignore BACKREF_FOUND_SHARED until all delayed
> +		 * refs have been checked.
> +		 */
> +		if (ret && (ret != BACKREF_FOUND_SHARED))
>  			break;
>  	}
> +	if (!ret)
> +		ret = extent_is_shared(sc);
> +out:
>  	spin_unlock(&head->lock);
>  	return ret;
>  }
>  
>  /*
>   * add all inline backrefs for bytenr to the list
> + *
> + * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
>   */
>  static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  			   struct btrfs_path *path, u64 bytenr,
>  			   int *info_level, struct preftrees *preftrees,
> -			   u64 *total_refs, u64 inum)
> +			   u64 *total_refs, struct share_check *sc)
>  {
>  	int ret = 0;
>  	int slot;
> @@ -884,7 +940,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  		case BTRFS_SHARED_BLOCK_REF_KEY:
>  			ret = add_direct_ref(fs_info, preftrees,
>  					     *info_level + 1, offset,
> -					     bytenr, 1, GFP_NOFS);
> +					     bytenr, 1, NULL, GFP_NOFS);
>  			break;
>  		case BTRFS_SHARED_DATA_REF_KEY: {
>  			struct btrfs_shared_data_ref *sdref;
> @@ -894,13 +950,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  			count = btrfs_shared_data_ref_count(leaf, sdref);
>  
>  			ret = add_direct_ref(fs_info, preftrees, 0, offset,
> -					     bytenr, count, GFP_NOFS);
> +					     bytenr, count, sc, GFP_NOFS);
>  			break;
>  		}
>  		case BTRFS_TREE_BLOCK_REF_KEY:
>  			ret = add_indirect_ref(fs_info, preftrees, offset,
>  					       NULL, *info_level + 1,
> -					       bytenr, 1, GFP_NOFS);
> +					       bytenr, 1, NULL, GFP_NOFS);
>  			break;
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
>  			struct btrfs_extent_data_ref *dref;
> @@ -914,7 +970,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  			key.type = BTRFS_EXTENT_DATA_KEY;
>  			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
>  
> -			if (inum && key.objectid != inum) {
> +			if (sc && sc->inum && key.objectid != sc->inum) {
>  				ret = BACKREF_FOUND_SHARED;
>  				break;
>  			}
> @@ -923,7 +979,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  
>  			ret = add_indirect_ref(fs_info, preftrees, root,
>  					       &key, 0, bytenr, count,
> -					       GFP_NOFS);
> +					       sc, GFP_NOFS);
>  			break;
>  		}
>  		default:
> @@ -939,11 +995,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
>  
>  /*
>   * add all non-inline backrefs for bytenr to the list
> + *
> + * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
>   */
>  static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			  struct btrfs_path *path, u64 bytenr,
>  			  int info_level, struct preftrees *preftrees,
> -			  u64 inum)
> +			  struct share_check *sc)
>  {
>  	struct btrfs_root *extent_root = fs_info->extent_root;
>  	int ret;
> @@ -976,7 +1034,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			/* SHARED DIRECT METADATA backref */
>  			ret = add_direct_ref(fs_info, preftrees,
>  					     info_level + 1, key.offset,
> -					     bytenr, 1, GFP_NOFS);
> +					     bytenr, 1, NULL, GFP_NOFS);
>  			break;
>  		case BTRFS_SHARED_DATA_REF_KEY: {
>  			/* SHARED DIRECT FULL backref */
> @@ -988,14 +1046,14 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			count = btrfs_shared_data_ref_count(leaf, sdref);
>  			ret = add_direct_ref(fs_info, preftrees, 0,
>  					     key.offset, bytenr, count,
> -					     GFP_NOFS);
> +					     sc, GFP_NOFS);
>  			break;
>  		}
>  		case BTRFS_TREE_BLOCK_REF_KEY:
>  			/* NORMAL INDIRECT METADATA backref */
>  			ret = add_indirect_ref(fs_info, preftrees, key.offset,
>  					       NULL, info_level + 1, bytenr,
> -					       1, GFP_NOFS);
> +					       1, NULL, GFP_NOFS);
>  			break;
>  		case BTRFS_EXTENT_DATA_REF_KEY: {
>  			/* NORMAL INDIRECT DATA backref */
> @@ -1011,7 +1069,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			key.type = BTRFS_EXTENT_DATA_KEY;
>  			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
>  
> -			if (inum && key.objectid != inum) {
> +			if (sc && sc->inum && key.objectid != sc->inum) {
>  				ret = BACKREF_FOUND_SHARED;
>  				break;
>  			}
> @@ -1019,7 +1077,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>  			root = btrfs_extent_data_ref_root(leaf, dref);
>  			ret = add_indirect_ref(fs_info, preftrees, root,
>  					       &key, 0, bytenr, count,
> -					       GFP_NOFS);
> +					       sc, GFP_NOFS);
>  			break;
>  		}
>  		default:
> @@ -1039,20 +1097,23 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>   * indirect refs to their parent bytenr.
>   * When roots are found, they're added to the roots list
>   *
> - * NOTE: This can return values > 0
> - *
>   * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
>   * much like trans == NULL case, the difference only lies in it will not
>   * commit root.
>   * The special case is for qgroup to search roots in commit_transaction().
>   *
> + * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
> + * shared extent is detected.
> + *
> + * Otherwise this returns 0 for success and <0 for an error.
> + *
>   * FIXME some caching might speed things up
>   */
>  static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  			     struct btrfs_fs_info *fs_info, u64 bytenr,
>  			     u64 time_seq, struct ulist *refs,
>  			     struct ulist *roots, const u64 *extent_item_pos,
> -			     u64 root_objectid, u64 inum)
> +			     struct share_check *sc)
>  {
>  	struct btrfs_key key;
>  	struct btrfs_path *path;
> @@ -1133,7 +1194,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  			}
>  			spin_unlock(&delayed_refs->lock);
>  			ret = add_delayed_refs(fs_info, head, time_seq,
> -					       &preftrees, &total_refs, inum);
> +					       &preftrees, &total_refs, sc);
>  			mutex_unlock(&head->mutex);
>  			if (ret)
>  				goto out;
> @@ -1155,11 +1216,11 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  		     key.type == BTRFS_METADATA_ITEM_KEY)) {
>  			ret = add_inline_refs(fs_info, path, bytenr,
>  					      &info_level, &preftrees,
> -					      &total_refs, inum);
> +					      &total_refs, sc);
>  			if (ret)
>  				goto out;
>  			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
> -					     &preftrees, inum);
> +					     &preftrees, sc);
>  			if (ret)
>  				goto out;
>  		}
> @@ -1174,8 +1235,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
>  
>  	ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
> -				    extent_item_pos, total_refs,
> -				    root_objectid);
> +				    extent_item_pos, total_refs, sc);
>  	if (ret)
>  		goto out;
>  
> @@ -1194,7 +1254,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
>  		node = rb_next(&ref->rbnode);
>  		WARN_ON(ref->count < 0);
>  		if (roots && ref->count && ref->root_id && ref->parent == 0) {
> -			if (root_objectid && ref->root_id != root_objectid) {
> +			if (sc && sc->root_objectid &&
> +			    ref->root_id != sc->root_objectid) {
>  				ret = BACKREF_FOUND_SHARED;
>  				goto out;
>  			}
> @@ -1298,7 +1359,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
>  		return -ENOMEM;
>  
>  	ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
> -				*leafs, NULL, extent_item_pos, 0, 0);
> +				*leafs, NULL, extent_item_pos, NULL);
>  	if (ret < 0 && ret != -ENOENT) {
>  		free_leaf_list(*leafs);
>  		return ret;
> @@ -1341,7 +1402,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
>  	ULIST_ITER_INIT(&uiter);
>  	while (1) {
>  		ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
> -					tmp, *roots, NULL, 0, 0);
> +					tmp, *roots, NULL, NULL);
>  		if (ret < 0 && ret != -ENOENT) {
>  			ulist_free(tmp);
>  			ulist_free(*roots);
> @@ -1397,6 +1458,11 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
>  	struct ulist_node *node;
>  	struct seq_list elem = SEQ_LIST_INIT(elem);
>  	int ret = 0;
> +	struct share_check shared = {
> +		.root_objectid = root->objectid,
> +		.inum = inum,
> +		.share_count = 0,
> +	};
>  
>  	tmp = ulist_alloc(GFP_NOFS);
>  	roots = ulist_alloc(GFP_NOFS);
> @@ -1417,7 +1483,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
>  	ULIST_ITER_INIT(&uiter);
>  	while (1) {
>  		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
> -					roots, NULL, root->objectid, inum);
> +					roots, NULL, &shared);
>  		if (ret == BACKREF_FOUND_SHARED) {
>  			/* this is the only condition under which we return 1 */
>  			ret = 1;
> -- 
> 2.10.2
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html