[RFC PATCH 00/11] Qgroup: new record/write/record infrastructure to record correct old/new_roots.

[RFC PATCH 00/11] Qgroup: new record/write/record infrastructure to record correct old/new_roots.

[Qu Wenruo]

[BUG]
https://patchwork.kernel.org/patch/6015791/
The above test case shows a bug caused by incorrect old/new_roots.
And the incorrect old/new_roots is caused by the incorrect timing
calling btrfs_find_all_roots().

[FIX]
This patchset try to fix it using a new routine for recording delayed
ref changes:
	Old			|	New
				|record old_roots
Run delayed_ref_node operation	|Run delayed_ref_node operation
Record_ref()			|Record_ref()
				|  |- record new_roots
...				|...

delayed_qgroup_accounting()	|delayed_qgroup_accounting()
  |- record new_roots		|  |
  |- update old_refcnt using	|  |- update old_refcnt using
  |  complicated logic		|  |  old_roots list
  |- update new_refcnt using	|  |- update new_refcnt using
     new_roots			|     new_roots list

Since we record old_roots before we do delayed_ref_node operation, so
the old_roots should be accurate(*), and we won't have the problem of
the old implement, where old/new_roots is recorded too late.

*: In fact, not completely correct, explained in CONS 1) and TODO
[PROS]
1) More generic code for old/new_refcnt.
As we have old/new_roots, update routine for old/new refcnt can be
merged into one generic code.

2) More generic code for rescan
For rescan case, we don't need the special flag anymore, just pass NULL
as old_roots and every thing is done.

3) Possible generic code for both shared/exclusive extents.
Infrastructure in this patch can handle exclusive extents without much
change.
Since old_roots will be empty and new_roots will contain the only root
referring to the exclusive extent, no need for special exclusive case.

[CONS]
1) Harder fix for Liu Bo's btrfs/017 test case.
Even with this patchset, ref_node still don't a "minor" sequence number
for us to judgment which node is inserted first.
Current seq in ref_node is just "major" sequence number and it won't
help in btrfs/017, since all node's sequence number is the same.

2) Much lower pass rate on btrfs/057.
The pass rate drops greatly on btrfs/057.
Not sure why, but is highly possible related to 1).


[TODO]
1) Try to cover exclusive extent case.
If I find something may cause problem in exclusive extent routine, then
it should also be covered by the infrastructure.

2) Reintroduce minor sequence number.
To solve CONS 1).

3) Continue investigate the infamous btrfs/057 case.

[PATCHSET STRUCTURE]
Patch 1 is the already sent patch, just resend it.
Patch 2~6 are parameter/member changes, providing the basis for later
patchse.
Patch 7~9 are the core infrastructure changes.
Patch 10 is self-test change to use the new infrastructure.
Patch 11 is cleanup.(Just press d!)

Qu Wenruo (11):
  btrfs: qgroup: Cleanup open-coded old/new_refcnt update and read.
  btrfs: extent-tree: Use ref_node to replace unneeded parameters in    
    __inc_extent_ref() and __free_extent()
  btrfs: backref: Add nolock option for btrfs_find_all_roots().
  btrfs: backref: Allow find_parent_nodes() to skip given ref_node.
  btrfs: backref: Allow btrfs_find_all_roots() to skip given ref_node.
  btrfs: qgroup: Add needed parameter and member for qgroup.
  btrfs: qgroup: save and pass old_roots ulist to    
    btrfs_qgroup_record_ref().
  btrfs: qgroup: Record current referenced roots at qgroup_record_ref().
  btrfs: qgroup: Use oper->old/new_roots to update refcnt.
  btrfs: qgroup-tests: Add old_roots ulist to allow qgroup test pass.
  btrfs: qgroup: Cleanup the unneeded codes.

 fs/btrfs/backref.c            |  70 +++++--
 fs/btrfs/backref.h            |   6 +-
 fs/btrfs/extent-tree.c        | 107 ++++++----
 fs/btrfs/ioctl.c              |   4 +-
 fs/btrfs/qgroup.c             | 471 +++++++++++++-----------------------------
 fs/btrfs/qgroup.h             |   7 +-
 fs/btrfs/tests/qgroup-tests.c |  38 +++-
 7 files changed, 299 insertions(+), 404 deletions(-)

-- 
2.3.3

[PATCH v2 RESEND 01/11] btrfs: qgroup: Cleanup open-coded old/new_refcnt update and read.

[Qu Wenruo]

Use inline functions to do such things, to improve readability.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Acked-by: David Sterba <dsterba@suse.cz>
---
v2:
  Change nameing to btrfs_qgroup_(update|get)_(old|new)_refcnt.
  Not use centeral qgroup_(get|update)_refcnt function, direct code into
  corresponding functions.
  Fix a forgot-to-replace bug.
---
 fs/btrfs/qgroup.c | 95 +++++++++++++++++++++++++++++++------------------------
 1 file changed, 54 insertions(+), 41 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 97159a8..6e7735d 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -84,11 +84,42 @@ struct btrfs_qgroup {
 
 	/*
 	 * temp variables for accounting operations
+	 * Refer to qgroup_shared_accouting() for details.
 	 */
 	u64 old_refcnt;
 	u64 new_refcnt;
 };
 
+static void btrfs_qgroup_update_old_refcnt(struct btrfs_qgroup *qg, u64 seq,
+					   int mod)
+{
+	if (qg->old_refcnt < seq)
+		qg->old_refcnt = seq;
+	qg->old_refcnt += mod;
+}
+
+static void btrfs_qgroup_update_new_refcnt(struct btrfs_qgroup *qg, u64 seq,
+					   int mod)
+{
+	if (qg->new_refcnt < seq)
+		qg->new_refcnt = seq;
+	qg->new_refcnt += mod;
+}
+
+static inline u64 btrfs_qgroup_get_old_refcnt(struct btrfs_qgroup *qg, u64 seq)
+{
+	if (qg->old_refcnt < seq)
+		return 0;
+	return qg->old_refcnt - seq;
+}
+
+static inline u64 btrfs_qgroup_get_new_refcnt(struct btrfs_qgroup *qg, u64 seq)
+{
+	if (qg->new_refcnt < seq)
+		return 0;
+	return qg->new_refcnt - seq;
+}
+
 /*
  * glue structure to represent the relations between qgroups.
  */
@@ -1497,6 +1528,7 @@ static int qgroup_calc_old_refcnt(struct btrfs_fs_info *fs_info,
 		ULIST_ITER_INIT(&tmp_uiter);
 		while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
 			struct btrfs_qgroup_list *glist;
+			int mod;
 
 			qg = u64_to_ptr(tmp_unode->aux);
 			/*
@@ -1508,20 +1540,15 @@ static int qgroup_calc_old_refcnt(struct btrfs_fs_info *fs_info,
 			 * upper level qgroups in order to determine exclusive
 			 * counts.
 			 *
-			 * For rescan we want to set old_refcnt to seq so our
-			 * exclusive calculations end up correct.
+			 * For rescan none of the extent is recorded before so
+			 * we just don't add old_refcnt.
 			 */
 			if (rescan)
-				qg->old_refcnt = seq;
-			else if (qg->old_refcnt < seq)
-				qg->old_refcnt = seq + 1;
-			else
-				qg->old_refcnt++;
-
-			if (qg->new_refcnt < seq)
-				qg->new_refcnt = seq + 1;
+				mod = 0;
 			else
-				qg->new_refcnt++;
+				mod = 1;
+			btrfs_qgroup_update_old_refcnt(qg, seq, mod);
+			btrfs_qgroup_update_new_refcnt(qg, seq, 1);
 			list_for_each_entry(glist, &qg->groups, next_group) {
 				ret = ulist_add(qgroups, glist->group->qgroupid,
 						ptr_to_u64(glist->group),
@@ -1615,14 +1642,8 @@ next:
 		struct btrfs_qgroup_list *glist;
 
 		qg = u64_to_ptr(unode->aux);
-		if (qg->old_refcnt < seq)
-			qg->old_refcnt = seq + 1;
-		else
-			qg->old_refcnt++;
-		if (qg->new_refcnt < seq)
-			qg->new_refcnt = seq + 1;
-		else
-			qg->new_refcnt++;
+		btrfs_qgroup_update_old_refcnt(qg, seq, 1);
+		btrfs_qgroup_update_new_refcnt(qg, seq, 1);
 		list_for_each_entry(glist, &qg->groups, next_group) {
 			ret = ulist_add(qgroups, glist->group->qgroupid,
 					ptr_to_u64(glist->group), GFP_ATOMIC);
@@ -1663,17 +1684,10 @@ static int qgroup_calc_new_refcnt(struct btrfs_fs_info *fs_info,
 		struct btrfs_qgroup_list *glist;
 
 		qg = u64_to_ptr(unode->aux);
-		if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED) {
-			if (qg->new_refcnt < seq)
-				qg->new_refcnt = seq + 1;
-			else
-				qg->new_refcnt++;
-		} else {
-			if (qg->old_refcnt < seq)
-				qg->old_refcnt = seq + 1;
-			else
-				qg->old_refcnt++;
-		}
+		if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED)
+			btrfs_qgroup_update_new_refcnt(qg, seq, 1);
+		else
+			btrfs_qgroup_update_old_refcnt(qg, seq, 1);
 		list_for_each_entry(glist, &qg->groups, next_group) {
 			ret = ulist_add(tmp, glist->group->qgroupid,
 					ptr_to_u64(glist->group), GFP_ATOMIC);
@@ -1706,11 +1720,14 @@ static int qgroup_adjust_counters(struct btrfs_fs_info *fs_info,
 		bool dirty = false;
 
 		qg = u64_to_ptr(unode->aux);
+		cur_old_count = btrfs_qgroup_get_old_refcnt(qg, seq);
+		cur_new_count = btrfs_qgroup_get_new_refcnt(qg, seq);
+
 		/*
 		 * Wasn't referenced before but is now, add to the reference
 		 * counters.
 		 */
-		if (qg->old_refcnt <= seq && qg->new_refcnt > seq) {
+		if (cur_old_count == 0 && cur_new_count > 0) {
 			qg->rfer += num_bytes;
 			qg->rfer_cmpr += num_bytes;
 			dirty = true;
@@ -1720,21 +1737,12 @@ static int qgroup_adjust_counters(struct btrfs_fs_info *fs_info,
 		 * Was referenced before but isn't now, subtract from the
 		 * reference counters.
 		 */
-		if (qg->old_refcnt > seq && qg->new_refcnt <= seq) {
+		if (cur_old_count > 0 && cur_new_count == 0) {
 			qg->rfer -= num_bytes;
 			qg->rfer_cmpr -= num_bytes;
 			dirty = true;
 		}
 
-		if (qg->old_refcnt < seq)
-			cur_old_count = 0;
-		else
-			cur_old_count = qg->old_refcnt - seq;
-		if (qg->new_refcnt < seq)
-			cur_new_count = 0;
-		else
-			cur_new_count = qg->new_refcnt - seq;
-
 		/*
 		 * If our refcount was the same as the roots previously but our
 		 * new count isn't the same as the number of roots now then we
@@ -1932,6 +1940,11 @@ static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 		new_roots = old_roots;
 		old_roots++;
 	}
+
+	/*
+	 * Bump qgroup_seq to avoid seq overlap
+	 * XXX: This makes qgroup_seq mismatch with oper->seq.
+	 */
 	fs_info->qgroup_seq += old_roots + 1;
 
 
-- 
2.3.3

[RFC PATCH 02/11] btrfs: extent-tree: Use ref_node to replace unneeded parameters in __inc_extent_ref() and __free_extent()

[Qu Wenruo]

__btrfs_inc_extent_ref() and __btrfs_free_extent() have already had too
many parameters, but three of them can be extracted from
btrfs_delayed_ref_node struct.

So use btrfs_delayed_ref_node struct as a single parameter to replace
the bytenr/num_byte/no_quota parameters.

The real objective of this patch is to allow btrfs_qgroup_record_ref()
get the node->seq in incoming qgroup patches.

Other functions calling btrfs_qgroup_record_ref() are not affected since
the rest will only add/sub exclusive extents, where node->seq is not
used.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 42 +++++++++++++++++++++---------------------
 1 file changed, 21 insertions(+), 21 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 571f402..89cb363 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -79,11 +79,10 @@ static int update_block_group(struct btrfs_trans_handle *trans,
 			      u64 num_bytes, int alloc);
 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
-				u64 bytenr, u64 num_bytes, u64 parent,
+				struct btrfs_delayed_ref_node *node, u64 parent,
 				u64 root_objectid, u64 owner_objectid,
 				u64 owner_offset, int refs_to_drop,
-				struct btrfs_delayed_extent_op *extra_op,
-				int no_quota);
+				struct btrfs_delayed_extent_op *extra_op);
 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
 				    struct extent_buffer *leaf,
 				    struct btrfs_extent_item *ei);
@@ -1967,10 +1966,9 @@ int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 
 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 				  struct btrfs_root *root,
-				  u64 bytenr, u64 num_bytes,
+				  struct btrfs_delayed_ref_node *node,
 				  u64 parent, u64 root_objectid,
 				  u64 owner, u64 offset, int refs_to_add,
-				  int no_quota,
 				  struct btrfs_delayed_extent_op *extent_op)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
@@ -1978,8 +1976,11 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	struct extent_buffer *leaf;
 	struct btrfs_extent_item *item;
 	struct btrfs_key key;
+	u64 bytenr = node->bytenr;
+	u64 num_bytes = node->num_bytes;
 	u64 refs;
 	int ret;
+	int no_quota = node->no_quota;
 	enum btrfs_qgroup_operation_type type = BTRFS_QGROUP_OPER_ADD_EXCL;
 
 	path = btrfs_alloc_path();
@@ -2087,17 +2088,15 @@ static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
 						 ref->objectid, ref->offset,
 						 &ins, node->ref_mod);
 	} else if (node->action == BTRFS_ADD_DELAYED_REF) {
-		ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
-					     node->num_bytes, parent,
+		ret = __btrfs_inc_extent_ref(trans, root, node, parent,
 					     ref_root, ref->objectid,
 					     ref->offset, node->ref_mod,
-					     node->no_quota, extent_op);
+					     extent_op);
 	} else if (node->action == BTRFS_DROP_DELAYED_REF) {
-		ret = __btrfs_free_extent(trans, root, node->bytenr,
-					  node->num_bytes, parent,
+		ret = __btrfs_free_extent(trans, root, node, parent,
 					  ref_root, ref->objectid,
 					  ref->offset, node->ref_mod,
-					  extent_op, node->no_quota);
+					  extent_op);
 	} else {
 		BUG();
 	}
@@ -2255,15 +2254,14 @@ static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
 						ref->level, &ins,
 						node->no_quota);
 	} else if (node->action == BTRFS_ADD_DELAYED_REF) {
-		ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
-					     node->num_bytes, parent, ref_root,
-					     ref->level, 0, 1, node->no_quota,
+		ret = __btrfs_inc_extent_ref(trans, root, node,
+					     parent, ref_root,
+					     ref->level, 0, 1,
 					     extent_op);
 	} else if (node->action == BTRFS_DROP_DELAYED_REF) {
-		ret = __btrfs_free_extent(trans, root, node->bytenr,
-					  node->num_bytes, parent, ref_root,
-					  ref->level, 0, 1, extent_op,
-					  node->no_quota);
+		ret = __btrfs_free_extent(trans, root, node,
+					  parent, ref_root,
+					  ref->level, 0, 1, extent_op);
 	} else {
 		BUG();
 	}
@@ -5785,11 +5783,10 @@ static void add_pinned_bytes(struct btrfs_fs_info *fs_info, u64 num_bytes,
 
 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
-				u64 bytenr, u64 num_bytes, u64 parent,
+				struct btrfs_delayed_ref_node *node, u64 parent,
 				u64 root_objectid, u64 owner_objectid,
 				u64 owner_offset, int refs_to_drop,
-				struct btrfs_delayed_extent_op *extent_op,
-				int no_quota)
+				struct btrfs_delayed_extent_op *extent_op)
 {
 	struct btrfs_key key;
 	struct btrfs_path *path;
@@ -5803,8 +5800,11 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 	int extent_slot = 0;
 	int found_extent = 0;
 	int num_to_del = 1;
+	int no_quota = node->no_quota;
 	u32 item_size;
 	u64 refs;
+	u64 bytenr = node->bytenr;
+	u64 num_bytes = node->num_bytes;
 	int last_ref = 0;
 	enum btrfs_qgroup_operation_type type = BTRFS_QGROUP_OPER_SUB_EXCL;
 	bool skinny_metadata = btrfs_fs_incompat(root->fs_info,
-- 
2.3.3

[RFC PATCH 03/11] btrfs: backref: Add nolock option for btrfs_find_all_roots().

[Qu Wenruo]

Add the "nolock" option for btrfs_find_all_roots().
This will allow btrfs_find_all_roots() to be called in
btrfs_qgroup_record_ref(), which will provide the basis for coming
qgroup patches.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/backref.c | 28 ++++++++++++++++++----------
 fs/btrfs/backref.h |  2 +-
 fs/btrfs/ioctl.c   |  2 +-
 fs/btrfs/qgroup.c  |  8 ++++----
 4 files changed, 24 insertions(+), 16 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index f55721f..6ef355e 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -880,13 +880,16 @@ 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
  *
+ * If nolock is set, it will consider the ref_head already locked and don't
+ * try to lock it.
+ *
  * 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)
+			     u64 root_objectid, u64 inum, int nolock)
 {
 	struct btrfs_key key;
 	struct btrfs_path *path;
@@ -944,7 +947,7 @@ again:
 		spin_lock(&delayed_refs->lock);
 		head = btrfs_find_delayed_ref_head(trans, bytenr);
 		if (head) {
-			if (!mutex_trylock(&head->mutex)) {
+			if (!nolock && !mutex_trylock(&head->mutex)) {
 				atomic_inc(&head->node.refs);
 				spin_unlock(&delayed_refs->lock);
 
@@ -963,7 +966,8 @@ again:
 			ret = __add_delayed_refs(head, time_seq,
 						 &prefs_delayed, &total_refs,
 						 inum);
-			mutex_unlock(&head->mutex);
+			if (!nolock)
+				mutex_unlock(&head->mutex);
 			if (ret)
 				goto out;
 		} else {
@@ -1124,7 +1128,8 @@ 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);
+				time_seq, *leafs, NULL, extent_item_pos,
+				0, 0, 0);
 	if (ret < 0 && ret != -ENOENT) {
 		free_leaf_list(*leafs);
 		return ret;
@@ -1148,7 +1153,8 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
  */
 static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 				  struct btrfs_fs_info *fs_info, u64 bytenr,
-				  u64 time_seq, struct ulist **roots)
+				  u64 time_seq, struct ulist **roots,
+				  int nolock)
 {
 	struct ulist *tmp;
 	struct ulist_node *node = NULL;
@@ -1167,7 +1173,8 @@ static int __btrfs_find_all_roots(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);
+					time_seq, tmp, *roots, NULL, 0, 0,
+					nolock);
 		if (ret < 0 && ret != -ENOENT) {
 			ulist_free(tmp);
 			ulist_free(*roots);
@@ -1186,13 +1193,14 @@ static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 bytenr,
-			 u64 time_seq, struct ulist **roots)
+			 u64 time_seq, struct ulist **roots, int nolock)
 {
 	int ret;
 
 	if (!trans)
 		down_read(&fs_info->commit_root_sem);
-	ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
+	ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots,
+				     nolock);
 	if (!trans)
 		up_read(&fs_info->commit_root_sem);
 	return ret;
@@ -1224,7 +1232,7 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans,
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
 		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
-					roots, NULL, root_objectid, inum);
+					roots, NULL, root_objectid, inum, 0);
 		if (ret == BACKREF_FOUND_SHARED) {
 			ret = 1;
 			break;
@@ -1635,7 +1643,7 @@ int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
 	ULIST_ITER_INIT(&ref_uiter);
 	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
 		ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
-					     tree_mod_seq_elem.seq, &roots);
+					     tree_mod_seq_elem.seq, &roots, 0);
 		if (ret)
 			break;
 		ULIST_ITER_INIT(&root_uiter);
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 9c41fba..f8acbd8 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -53,7 +53,7 @@ int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
 
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 bytenr,
-			 u64 time_seq, struct ulist **roots);
+			 u64 time_seq, struct ulist **roots, int nolock);
 char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
 			u32 name_len, unsigned long name_off,
 			struct extent_buffer *eb_in, u64 parent,
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 74609b9..d3391df 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -3050,7 +3050,7 @@ static int check_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 
 	btrfs_get_tree_mod_seq(root->fs_info, &tree_mod_seq_elem);
 	ret = btrfs_find_all_roots(trans, root->fs_info, disko,
-				   tree_mod_seq_elem.seq, &roots);
+				   tree_mod_seq_elem.seq, &roots, 0);
 	if (ret < 0)
 		goto out;
 	ret = 0;
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 6e7735d..c01bc6f 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1788,7 +1788,7 @@ static int check_existing_refs(struct btrfs_trans_handle *trans,
 	int ret = 0;
 
 	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
-				   oper->elem.seq, &roots);
+				   oper->elem.seq, &roots, 0);
 	if (ret < 0)
 		return ret;
 	ret = 0;
@@ -1879,7 +1879,7 @@ static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 
 	btrfs_get_tree_mod_seq(fs_info, &elem);
 	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr, elem.seq,
-				   &roots);
+				   &roots, 0);
 	btrfs_put_tree_mod_seq(fs_info, &elem);
 	if (ret < 0) {
 		ulist_free(qgroups);
@@ -1988,7 +1988,7 @@ static int qgroup_subtree_accounting(struct btrfs_trans_handle *trans,
 
 	btrfs_get_tree_mod_seq(fs_info, &elem);
 	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
-				   elem.seq, &roots);
+				   elem.seq, &roots, 0);
 	btrfs_put_tree_mod_seq(fs_info, &elem);
 	if (ret < 0)
 		goto out;
@@ -2590,7 +2590,7 @@ qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
 
 		ulist_reinit(qgroups);
 		ret = btrfs_find_all_roots(NULL, fs_info, found.objectid, 0,
-					   &roots);
+					   &roots, 0);
 		if (ret < 0)
 			goto out;
 		spin_lock(&fs_info->qgroup_lock);
-- 
2.3.3

[RFC PATCH 04/11] btrfs: backref: Allow find_parent_nodes() to skip given ref_node.

[Qu Wenruo]

This provides the basis for later implement to determine whether given
root has reference on a given extent before delayed_ref operation.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/backref.c | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6ef355e..7db848c 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -568,8 +568,9 @@ static void __merge_refs(struct list_head *head, int mode)
  * 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,
+static int __add_delayed_refs(struct btrfs_delayed_ref_head *head,
+			      struct btrfs_delayed_ref_node *node_to_skip,
+			      u64 seq, struct list_head *prefs, u64 *total_refs,
 			      u64 inum)
 {
 	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
@@ -589,6 +590,8 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 		node = rb_entry(n, struct btrfs_delayed_ref_node,
 				rb_node);
 		n = rb_next(n);
+		if (node_to_skip && node == node_to_skip)
+			continue;
 		if (node->seq > seq)
 			continue;
 
@@ -886,8 +889,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
  * 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 btrfs_fs_info *fs_info,
+			     struct btrfs_delayed_ref_node *node_to_skip,
+			     u64 bytenr, u64 time_seq, struct ulist *refs,
 			     struct ulist *roots, const u64 *extent_item_pos,
 			     u64 root_objectid, u64 inum, int nolock)
 {
@@ -963,7 +967,7 @@ again:
 				goto again;
 			}
 			spin_unlock(&delayed_refs->lock);
-			ret = __add_delayed_refs(head, time_seq,
+			ret = __add_delayed_refs(head, node_to_skip, time_seq,
 						 &prefs_delayed, &total_refs,
 						 inum);
 			if (!nolock)
@@ -1127,7 +1131,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
 	if (!*leafs)
 		return -ENOMEM;
 
-	ret = find_parent_nodes(trans, fs_info, bytenr,
+	ret = find_parent_nodes(trans, fs_info, NULL, bytenr,
 				time_seq, *leafs, NULL, extent_item_pos,
 				0, 0, 0);
 	if (ret < 0 && ret != -ENOENT) {
@@ -1172,7 +1176,7 @@ static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
-		ret = find_parent_nodes(trans, fs_info, bytenr,
+		ret = find_parent_nodes(trans, fs_info, NULL, bytenr,
 					time_seq, tmp, *roots, NULL, 0, 0,
 					nolock);
 		if (ret < 0 && ret != -ENOENT) {
@@ -1231,8 +1235,9 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans,
 		down_read(&fs_info->commit_root_sem);
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
-		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
-					roots, NULL, root_objectid, inum, 0);
+		ret = find_parent_nodes(trans, fs_info, NULL, bytenr, elem.seq,
+					tmp, roots, NULL, root_objectid, inum,
+					0);
 		if (ret == BACKREF_FOUND_SHARED) {
 			ret = 1;
 			break;
-- 
2.3.3

[RFC PATCH 05/11] btrfs: backref: Allow btrfs_find_all_roots() to skip given ref_node.

[Qu Wenruo]

This feature is used in incoming qgroup patches to resolve whether a
given root has reference to a extent before the delayed_ref operation.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/backref.c | 21 +++++++++++++--------
 fs/btrfs/backref.h |  6 ++++--
 fs/btrfs/ioctl.c   |  2 +-
 fs/btrfs/qgroup.c  | 10 +++++-----
 4 files changed, 23 insertions(+), 16 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 7db848c..e33a003 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -1156,8 +1156,10 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
  * returns 0 on success, < 0 on error.
  */
 static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
-				  struct btrfs_fs_info *fs_info, u64 bytenr,
-				  u64 time_seq, struct ulist **roots,
+				  struct btrfs_fs_info *fs_info,
+				  struct btrfs_delayed_ref_node *node_to_skip,
+				  u64 bytenr, u64 time_seq,
+				  struct ulist **roots,
 				  int nolock)
 {
 	struct ulist *tmp;
@@ -1176,7 +1178,7 @@ static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 
 	ULIST_ITER_INIT(&uiter);
 	while (1) {
-		ret = find_parent_nodes(trans, fs_info, NULL, bytenr,
+		ret = find_parent_nodes(trans, fs_info, node_to_skip, bytenr,
 					time_seq, tmp, *roots, NULL, 0, 0,
 					nolock);
 		if (ret < 0 && ret != -ENOENT) {
@@ -1196,15 +1198,17 @@ static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 }
 
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
-			 struct btrfs_fs_info *fs_info, u64 bytenr,
-			 u64 time_seq, struct ulist **roots, int nolock)
+			 struct btrfs_fs_info *fs_info,
+			 struct btrfs_delayed_ref_node *node_to_skip,
+			 u64 bytenr, u64 time_seq,
+			 struct ulist **roots, int nolock)
 {
 	int ret;
 
 	if (!trans)
 		down_read(&fs_info->commit_root_sem);
-	ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots,
-				     nolock);
+	ret = __btrfs_find_all_roots(trans, fs_info, node_to_skip, bytenr,
+				     time_seq, roots, nolock);
 	if (!trans)
 		up_read(&fs_info->commit_root_sem);
 	return ret;
@@ -1647,7 +1651,8 @@ int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
 
 	ULIST_ITER_INIT(&ref_uiter);
 	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
-		ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
+		ret = __btrfs_find_all_roots(trans, fs_info, NULL,
+					     ref_node->val,
 					     tree_mod_seq_elem.seq, &roots, 0);
 		if (ret)
 			break;
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index f8acbd8..0b33483 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -52,8 +52,10 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
 
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
-			 struct btrfs_fs_info *fs_info, u64 bytenr,
-			 u64 time_seq, struct ulist **roots, int nolock);
+			 struct btrfs_fs_info *fs_info,
+			 struct btrfs_delayed_ref_node *node_to_skip,
+			 u64 bytenr, u64 time_seq, struct ulist **roots,
+			 int nolock);
 char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
 			u32 name_len, unsigned long name_off,
 			struct extent_buffer *eb_in, u64 parent,
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index d3391df..fc8cee3 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -3049,7 +3049,7 @@ static int check_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		return 1;
 
 	btrfs_get_tree_mod_seq(root->fs_info, &tree_mod_seq_elem);
-	ret = btrfs_find_all_roots(trans, root->fs_info, disko,
+	ret = btrfs_find_all_roots(trans, root->fs_info, NULL, disko,
 				   tree_mod_seq_elem.seq, &roots, 0);
 	if (ret < 0)
 		goto out;
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index c01bc6f..9a94494 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1787,7 +1787,7 @@ static int check_existing_refs(struct btrfs_trans_handle *trans,
 	struct ulist_iterator uiter;
 	int ret = 0;
 
-	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
+	ret = btrfs_find_all_roots(trans, fs_info, NULL, oper->bytenr,
 				   oper->elem.seq, &roots, 0);
 	if (ret < 0)
 		return ret;
@@ -1878,7 +1878,7 @@ static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 	}
 
 	btrfs_get_tree_mod_seq(fs_info, &elem);
-	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr, elem.seq,
+	ret = btrfs_find_all_roots(trans, fs_info, NULL, oper->bytenr, elem.seq,
 				   &roots, 0);
 	btrfs_put_tree_mod_seq(fs_info, &elem);
 	if (ret < 0) {
@@ -1987,7 +1987,7 @@ static int qgroup_subtree_accounting(struct btrfs_trans_handle *trans,
 		return -ENOMEM;
 
 	btrfs_get_tree_mod_seq(fs_info, &elem);
-	ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
+	ret = btrfs_find_all_roots(trans, fs_info, NULL, oper->bytenr,
 				   elem.seq, &roots, 0);
 	btrfs_put_tree_mod_seq(fs_info, &elem);
 	if (ret < 0)
@@ -2589,8 +2589,8 @@ qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
 			num_bytes = found.offset;
 
 		ulist_reinit(qgroups);
-		ret = btrfs_find_all_roots(NULL, fs_info, found.objectid, 0,
-					   &roots, 0);
+		ret = btrfs_find_all_roots(NULL, fs_info, NULL, found.objectid,
+					   0, &roots, 0);
 		if (ret < 0)
 			goto out;
 		spin_lock(&fs_info->qgroup_lock);
-- 
2.3.3

[RFC PATCH 06/11] btrfs: qgroup: Add needed parameter and member for qgroup.

[Qu Wenruo]

Add the following member for struct btrfs_qgroup_operation:
  'old_roots' ulist
    Records rootfs found before the delayed ref operation.

  'new_roots' ulist
    Records rootfs found after the delayed ref operation.

Add the following parameters for btrfs_qgroup_record_ref():
  'old_roots' ulist
    Records rootfs found before the delayed ref operation.
    Caller of btrfs_qgroup_record_ref() should get the old_roots ulist
    before writing extent tree and pass it to qgroup_record_ref() if it
    may cause a shared extent accounting operation.

  'node_seq' u64
    Sequence number of the correspoding delayed ref node.
    Used to search delayed refs to find correct reference roots.

This patch just adds the member and parameters, no real behavior changes.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c        | 33 ++++++++++++++++++---------------
 fs/btrfs/qgroup.c             | 13 +++++++++++--
 fs/btrfs/qgroup.h             |  7 +++++--
 fs/btrfs/tests/qgroup-tests.c | 10 +++++-----
 4 files changed, 39 insertions(+), 24 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 89cb363..e73c1fa 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -2013,8 +2013,9 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 			type = BTRFS_QGROUP_OPER_ADD_SHARED;
 		btrfs_release_path(path);
 
-		ret = btrfs_qgroup_record_ref(trans, fs_info, root_objectid,
-					      bytenr, num_bytes, type, 0);
+		ret = btrfs_qgroup_record_ref(trans, fs_info, NULL,
+					      root_objectid, bytenr, num_bytes,
+					      node->seq, type, 0);
 		goto out;
 	}
 
@@ -2037,8 +2038,9 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	btrfs_release_path(path);
 
 	if (!no_quota) {
-		ret = btrfs_qgroup_record_ref(trans, fs_info, root_objectid,
-					      bytenr, num_bytes, type, 0);
+		ret = btrfs_qgroup_record_ref(trans, fs_info, NULL,
+					      root_objectid, bytenr, num_bytes,
+					      node->seq, type, 0);
 		if (ret)
 			goto out;
 	}
@@ -6057,9 +6059,9 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 		    type == BTRFS_QGROUP_OPER_SUB_SHARED)
 			mod_seq = 1;
 
-		ret = btrfs_qgroup_record_ref(trans, info, root_objectid,
-					      bytenr, num_bytes, type,
-					      mod_seq);
+		ret = btrfs_qgroup_record_ref(trans, info, NULL, root_objectid,
+					      bytenr, num_bytes, node->seq,
+					      type, mod_seq);
 	}
 out:
 	btrfs_free_path(path);
@@ -6997,8 +6999,8 @@ static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
 	btrfs_free_path(path);
 
 	/* Always set parent to 0 here since its exclusive anyway. */
-	ret = btrfs_qgroup_record_ref(trans, fs_info, root_objectid,
-				      ins->objectid, ins->offset,
+	ret = btrfs_qgroup_record_ref(trans, fs_info, NULL, root_objectid,
+				      ins->objectid, ins->offset, 0,
 				      BTRFS_QGROUP_OPER_ADD_EXCL, 0);
 	if (ret)
 		return ret;
@@ -7085,8 +7087,9 @@ static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
 	btrfs_free_path(path);
 
 	if (!no_quota) {
-		ret = btrfs_qgroup_record_ref(trans, fs_info, root_objectid,
-					      ins->objectid, num_bytes,
+		ret = btrfs_qgroup_record_ref(trans, fs_info, NULL,
+					      root_objectid, ins->objectid,
+					      num_bytes, 0,
 					      BTRFS_QGROUP_OPER_ADD_EXCL, 0);
 		if (ret)
 			return ret;
@@ -7463,8 +7466,8 @@ static int account_leaf_items(struct btrfs_trans_handle *trans,
 		num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 
 		ret = btrfs_qgroup_record_ref(trans, root->fs_info,
-					      root->objectid,
-					      bytenr, num_bytes,
+					      NULL, root->objectid,
+					      bytenr, num_bytes, 0,
 					      BTRFS_QGROUP_OPER_SUB_SUBTREE, 0);
 		if (ret)
 			return ret;
@@ -7611,9 +7614,9 @@ walk_down:
 			path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
 
 			ret = btrfs_qgroup_record_ref(trans, root->fs_info,
-						root->objectid,
+						NULL, root->objectid,
 						child_bytenr,
-						root->nodesize,
+						root->nodesize, 0,
 						BTRFS_QGROUP_OPER_SUB_SUBTREE,
 						0);
 			if (ret)
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 9a94494..b82c43c 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1335,9 +1335,13 @@ static int insert_qgroup_oper(struct btrfs_fs_info *fs_info,
  * Record a quota operation for processing later on.
  * @trans: the transaction we are adding the delayed op to.
  * @fs_info: the fs_info for this fs.
+ * @old_roots: roots referring the extent before the delayed_ref operation.
+ *	       Only used for shared extents accounting.
  * @ref_root: the root of the reference we are acting on,
  * @bytenr: the bytenr we are acting on.
  * @num_bytes: the number of bytes in the reference.
+ * @node_seq: sequence number of corresponding ref_node.
+ *	      Only used for shared extents accounting.
  * @type: the type of operation this is.
  * @mod_seq: do we need to get a sequence number for looking up roots.
  *
@@ -1348,8 +1352,9 @@ static int insert_qgroup_oper(struct btrfs_fs_info *fs_info,
  * MUST BE HOLDING THE REF LOCK.
  */
 int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
-			    struct btrfs_fs_info *fs_info, u64 ref_root,
-			    u64 bytenr, u64 num_bytes,
+			    struct btrfs_fs_info *fs_info,
+			    struct ulist *old_roots, u64 ref_root,
+			    u64 bytenr, u64 num_bytes, u64 node_seq,
 			    enum btrfs_qgroup_operation_type type, int mod_seq)
 {
 	struct btrfs_qgroup_operation *oper;
@@ -1366,6 +1371,8 @@ int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
 	oper->bytenr = bytenr;
 	oper->num_bytes = num_bytes;
 	oper->type = type;
+	oper->new_roots = NULL;
+	oper->old_roots = old_roots;
 	oper->seq = atomic_inc_return(&fs_info->qgroup_op_seq);
 	INIT_LIST_HEAD(&oper->elem.list);
 	oper->elem.seq = 0;
@@ -2135,6 +2142,8 @@ int btrfs_delayed_qgroup_accounting(struct btrfs_trans_handle *trans,
 		rb_erase(&oper->n, &fs_info->qgroup_op_tree);
 		spin_unlock(&fs_info->qgroup_op_lock);
 		btrfs_put_tree_mod_seq(fs_info, &oper->elem);
+		ulist_free(oper->old_roots);
+		ulist_free(oper->new_roots);
 		kfree(oper);
 	}
 	return ret;
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 18cc68c..264b498 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -56,6 +56,8 @@ struct btrfs_qgroup_operation {
 	struct seq_list elem;
 	struct rb_node n;
 	struct list_head list;
+	struct ulist *old_roots;
+	struct ulist *new_roots;
 };
 
 int btrfs_quota_enable(struct btrfs_trans_handle *trans,
@@ -81,8 +83,9 @@ int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info);
 void btrfs_free_qgroup_config(struct btrfs_fs_info *fs_info);
 struct btrfs_delayed_extent_op;
 int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
-			    struct btrfs_fs_info *fs_info, u64 ref_root,
-			    u64 bytenr, u64 num_bytes,
+			    struct btrfs_fs_info *fs_info,
+			    struct ulist *old_roots, u64 ref_root,
+			    u64 bytenr, u64 num_bytes, u64 node_seq,
 			    enum btrfs_qgroup_operation_type type,
 			    int mod_seq);
 int btrfs_delayed_qgroup_accounting(struct btrfs_trans_handle *trans,
diff --git a/fs/btrfs/tests/qgroup-tests.c b/fs/btrfs/tests/qgroup-tests.c
index 73f299e..c97c5f8 100644
--- a/fs/btrfs/tests/qgroup-tests.c
+++ b/fs/btrfs/tests/qgroup-tests.c
@@ -238,7 +238,7 @@ static int test_no_shared_qgroup(struct btrfs_root *root)
 		return ret;
 	}
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, 5, 4096, 4096,
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 5, 4096, 4096, 0,
 				      BTRFS_QGROUP_OPER_ADD_EXCL, 0);
 	if (ret) {
 		test_msg("Couldn't add space to a qgroup %d\n", ret);
@@ -264,7 +264,7 @@ static int test_no_shared_qgroup(struct btrfs_root *root)
 	if (ret)
 		return -EINVAL;
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, 5, 4096, 4096,
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 5, 4096, 4096, 0,
 				      BTRFS_QGROUP_OPER_SUB_EXCL, 0);
 	if (ret) {
 		test_msg("Couldn't remove space from the qgroup %d\n", ret);
@@ -311,7 +311,7 @@ static int test_multiple_refs(struct btrfs_root *root)
 	if (ret)
 		return ret;
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, 5, 4096, 4096,
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 5, 4096, 4096, 0,
 				      BTRFS_QGROUP_OPER_ADD_EXCL, 0);
 	if (ret) {
 		test_msg("Couldn't add space to a qgroup %d\n", ret);
@@ -333,7 +333,7 @@ static int test_multiple_refs(struct btrfs_root *root)
 	if (ret)
 		return ret;
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, 256, 4096, 4096,
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 256, 4096, 4096, 0,
 				      BTRFS_QGROUP_OPER_ADD_SHARED, 0);
 	if (ret) {
 		test_msg("Qgroup record ref failed %d\n", ret);
@@ -360,7 +360,7 @@ static int test_multiple_refs(struct btrfs_root *root)
 	if (ret)
 		return ret;
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, 256, 4096, 4096,
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 256, 4096, 4096, 0,
 				      BTRFS_QGROUP_OPER_SUB_SHARED, 0);
 	if (ret) {
 		test_msg("Qgroup record ref failed %d\n", ret);
-- 
2.3.3

[RFC PATCH 07/11] btrfs: qgroup: save and pass old_roots ulist to btrfs_qgroup_record_ref().

[Qu Wenruo]

For possible shared extent accounting case, call btrfs_find_all_roots()
before we write backref data into extent tree to find exactly how many
roots is referring the extent as old_roots.

And pass it to btrfs_qgroup_record_ref() for later operations.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 42 +++++++++++++++++++++++++++++++++++++-----
 1 file changed, 37 insertions(+), 5 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index e73c1fa..e3e7509 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -36,6 +36,8 @@
 #include "math.h"
 #include "sysfs.h"
 #include "qgroup.h"
+#include "ulist.h"
+#include "backref.h"
 
 #undef SCRAMBLE_DELAYED_REFS
 
@@ -1976,11 +1978,13 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	struct extent_buffer *leaf;
 	struct btrfs_extent_item *item;
 	struct btrfs_key key;
+	struct ulist *old_roots = NULL;
 	u64 bytenr = node->bytenr;
 	u64 num_bytes = node->num_bytes;
 	u64 refs;
 	int ret;
 	int no_quota = node->no_quota;
+	int need_to_free_old_roots = 0;
 	enum btrfs_qgroup_operation_type type = BTRFS_QGROUP_OPER_ADD_EXCL;
 
 	path = btrfs_alloc_path();
@@ -1990,6 +1994,14 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	if (!is_fstree(root_objectid) || !root->fs_info->quota_enabled)
 		no_quota = 1;
 
+	if (!no_quota) {
+		need_to_free_old_roots = 1;
+		ret = btrfs_find_all_roots(trans, fs_info, node, bytenr,
+					   node->seq, &old_roots, 1);
+		if (ret < 0)
+			goto out;
+	}
+
 	path->reada = 1;
 	path->leave_spinning = 1;
 	/* this will setup the path even if it fails to insert the back ref */
@@ -2013,9 +2025,11 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 			type = BTRFS_QGROUP_OPER_ADD_SHARED;
 		btrfs_release_path(path);
 
-		ret = btrfs_qgroup_record_ref(trans, fs_info, NULL,
+		ret = btrfs_qgroup_record_ref(trans, fs_info, old_roots,
 					      root_objectid, bytenr, num_bytes,
 					      node->seq, type, 0);
+		if (!ret)
+			need_to_free_old_roots = 0;
 		goto out;
 	}
 
@@ -2038,11 +2052,13 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	btrfs_release_path(path);
 
 	if (!no_quota) {
-		ret = btrfs_qgroup_record_ref(trans, fs_info, NULL,
+		ret = btrfs_qgroup_record_ref(trans, fs_info, old_roots,
 					      root_objectid, bytenr, num_bytes,
 					      node->seq, type, 0);
 		if (ret)
 			goto out;
+		else
+			need_to_free_old_roots = 0;
 	}
 
 	path->reada = 1;
@@ -2054,6 +2070,8 @@ static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	if (ret)
 		btrfs_abort_transaction(trans, root, ret);
 out:
+	if (need_to_free_old_roots)
+		ulist_free(old_roots);
 	btrfs_free_path(path);
 	return ret;
 }
@@ -5797,12 +5815,14 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 	struct extent_buffer *leaf;
 	struct btrfs_extent_item *ei;
 	struct btrfs_extent_inline_ref *iref;
+	struct ulist *old_roots = NULL;
 	int ret;
 	int is_data;
 	int extent_slot = 0;
 	int found_extent = 0;
 	int num_to_del = 1;
 	int no_quota = node->no_quota;
+	int need_to_free_old_roots = 0;
 	u32 item_size;
 	u64 refs;
 	u64 bytenr = node->bytenr;
@@ -5819,6 +5839,14 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 	if (!path)
 		return -ENOMEM;
 
+	if (!no_quota) {
+		need_to_free_old_roots = 1;
+		ret = btrfs_find_all_roots(trans, root->fs_info, node, bytenr,
+					   node->seq, &old_roots, 1);
+		if (ret < 0)
+			goto out;
+	}
+
 	path->reada = 1;
 	path->leave_spinning = 1;
 
@@ -6059,11 +6087,15 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
 		    type == BTRFS_QGROUP_OPER_SUB_SHARED)
 			mod_seq = 1;
 
-		ret = btrfs_qgroup_record_ref(trans, info, NULL, root_objectid,
-					      bytenr, num_bytes, node->seq,
-					      type, mod_seq);
+		ret = btrfs_qgroup_record_ref(trans, info, old_roots,
+					      root_objectid, bytenr, num_bytes,
+					      node->seq, type, mod_seq);
+		if (!ret)
+			need_to_free_old_roots = 0;
 	}
 out:
+	if (need_to_free_old_roots)
+		ulist_free(old_roots);
 	btrfs_free_path(path);
 	return ret;
 }
-- 
2.3.3

[RFC PATCH 08/11] btrfs: qgroup: Record current referenced roots at qgroup_record_ref().

[Qu Wenruo]

One of problems in old qgroup is, we can only get a view on the final
results when we are going to adjust qgroup accounting.

This makes the following operataion get wrong result:
1. Subvol 257 add an exclusive extent A.
2. Subvol 258 add a shared reference to extent A.
3. Subvol 259 add a shared reference to extent A.
4. Sync

Subvol 258 and 259's qgroup data is consistent, but subvol 257 still
have exclusive reference on extent A.

The problem happens on step 2, where we should decrease exclusive
reference number, but old implement just record the operation type,
and let qgroup get roots reference number at step 4, where extent A is
finally referred by 3 roots.

At the time quota running, it can only see the final result, extent A is
referred by 3 roots (new_refcnt = 3) and before that, referred by 2
roots(old_refcnt = 2).
Quota will only decrease exclusive refer when old_refcnt == old_roots.
However in that case, old_refcnt is the final one, not the one in before
step 2, causing the exclusive counts of 257 untouched.

This patch will records root reference counts at qgroup_record_ref()
timing, which will give correct result.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index b82c43c..4ad4106 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1379,6 +1379,14 @@ int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
 
 	trace_btrfs_qgroup_record_ref(oper);
 
+	if (type == BTRFS_QGROUP_OPER_ADD_SHARED ||
+	    type == BTRFS_QGROUP_OPER_SUB_SHARED) {
+		ret = btrfs_find_all_roots(trans, fs_info, NULL, bytenr, node_seq,
+					   &oper->new_roots, 1);
+		if (ret < 0)
+			goto out;
+	}
+
 	if (type == BTRFS_QGROUP_OPER_SUB_SUBTREE) {
 		/*
 		 * If any operation for this bytenr/ref_root combo
@@ -1390,8 +1398,8 @@ int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
 		 * drop snapshot.
 		 */
 		if (qgroup_oper_exists(fs_info, oper)) {
-			kfree(oper);
-			return 0;
+			ret = 0;
+			goto out;
 		}
 	}
 
@@ -1399,8 +1407,7 @@ int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
 	if (ret) {
 		/* Shouldn't happen so have an assert for developers */
 		ASSERT(0);
-		kfree(oper);
-		return ret;
+		goto out;
 	}
 	list_add_tail(&oper->list, &trans->qgroup_ref_list);
 
@@ -1408,6 +1415,11 @@ int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
 		btrfs_get_tree_mod_seq(fs_info, &oper->elem);
 
 	return 0;
+out:
+	if (ret < 0)
+		ulist_free(oper->new_roots);
+	kfree(oper);
+	return ret;
 }
 
 /*
-- 
2.3.3

[RFC PATCH 09/11] btrfs: qgroup: Use oper->old/new_roots to update refcnt.

[Qu Wenruo]

1) Use accurate old/new_roots in btrfs_qgroup_operation.
Old implement uses find_all_roots() to get a roots referring to given
bytenr.
But the problem is, at the timing of btrfs_delayed_qgroup_accounting(),
it's too late and we can only get final result of all delayed_ref
operations.

Thanks to previous patches, we have old_roots which restored the correct
roots got from calling find_all_roots() before we write backref to
extent tree and skip the current running ref_node.
And new_roots is got from calling find_all_roots() just after we write
backref to extent tree.

So we have accurate results than the old implement.

2) Use same routine to handle old/new_refcnt.
The old routine uses different routine for old/new_refcnt update, which
is a duplication of codes and takes extra time to maintain.

3) No more special case for rescan.
Old implement adds some special case for rescan, but now we don't need
them anymore.
Just set old_roots to NULL should allow rescan to get correct result.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 210 ++++++++++++++++++++++++++++++------------------------
 1 file changed, 115 insertions(+), 95 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 4ad4106..16240e6 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -84,7 +84,7 @@ struct btrfs_qgroup {
 
 	/*
 	 * temp variables for accounting operations
-	 * Refer to qgroup_shared_accouting() for details.
+	 * Refer to qgroup_shared_accounting() for details.
 	 */
 	u64 old_refcnt;
 	u64 new_refcnt;
@@ -1501,10 +1501,69 @@ out:
 	return ret;
 }
 
+
+#define UPDATE_NEW	0
+#define UPDATE_OLD	1
 /*
  * Walk all of the roots that pointed to our bytenr and adjust their refcnts as
  * properly.
  */
+static int qgroup_update_refcnt(struct btrfs_fs_info *fs_info,
+				struct ulist *roots,
+				struct ulist *tmp,
+				struct ulist *qgroups,
+				u64 seq, int update_old)
+{
+	struct ulist_node *unode;
+	struct ulist_iterator uiter;
+	struct ulist_node *tmp_unode;
+	struct ulist_iterator tmp_uiter;
+	struct btrfs_qgroup *qg;
+	int ret;
+
+	if (!roots)
+		return 0;
+
+	ULIST_ITER_INIT(&uiter);
+	while ((unode = ulist_next(roots, &uiter))) {
+		qg = find_qgroup_rb(fs_info, unode->val);
+		if (!qg)
+			continue;
+
+		ulist_reinit(tmp);
+		ret = ulist_add(qgroups, qg->qgroupid, ptr_to_u64(qg),
+				GFP_ATOMIC);
+		if (ret < 0)
+			return ret;
+		ret = ulist_add(tmp, qg->qgroupid, ptr_to_u64(qg), GFP_ATOMIC);
+		if (ret < 0)
+			return ret;
+		ULIST_ITER_INIT(&tmp_uiter);
+		while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
+			struct btrfs_qgroup_list *glist;
+
+			qg = u64_to_ptr(tmp_unode->aux);
+			if (update_old)
+				btrfs_qgroup_update_old_refcnt(qg, seq, 1);
+			else
+				btrfs_qgroup_update_new_refcnt(qg, seq, 1);
+			list_for_each_entry(glist, &qg->groups, next_group) {
+				ret = ulist_add(qgroups, glist->group->qgroupid,
+						ptr_to_u64(glist->group),
+						GFP_ATOMIC);
+				if (ret < 0)
+					return ret;
+				ret = ulist_add(tmp, glist->group->qgroupid,
+						ptr_to_u64(glist->group),
+						GFP_ATOMIC);
+				if (ret < 0)
+					return ret;
+			}
+		}
+	}
+	return 0;
+}
+
 static int qgroup_calc_old_refcnt(struct btrfs_fs_info *fs_info,
 				  u64 root_to_skip, struct ulist *tmp,
 				  struct ulist *roots, struct ulist *qgroups,
@@ -1725,14 +1784,20 @@ static int qgroup_calc_new_refcnt(struct btrfs_fs_info *fs_info,
  * This adjusts the counters for all referenced qgroups if need be.
  */
 static int qgroup_adjust_counters(struct btrfs_fs_info *fs_info,
-				  u64 root_to_skip, u64 num_bytes,
-				  struct ulist *qgroups, u64 seq,
-				  int old_roots, int new_roots, int rescan)
+				  struct ulist *qgroups,
+				  struct ulist *old_root_list,
+				  struct ulist *new_root_list,
+				  u64 num_bytes, u64 seq)
 {
 	struct ulist_node *unode;
 	struct ulist_iterator uiter;
 	struct btrfs_qgroup *qg;
 	u64 cur_new_count, cur_old_count;
+	u64 old_roots = 0;
+	u64 new_roots = new_root_list->nnodes;
+
+	if (old_root_list)
+		old_roots = old_root_list->nnodes;
 
 	ULIST_ITER_INIT(&uiter);
 	while ((unode = ulist_next(qgroups, &uiter))) {
@@ -1836,19 +1901,12 @@ static int check_existing_refs(struct btrfs_trans_handle *trans,
  * jack this sequence up by the number of roots we found each time in order to
  * make sure we don't have any overlap.
  *
- * 2) We first search all the roots that reference the area _except_ the root
- * we're acting on currently.  This makes up the old_refcnt of all the qgroups
- * before.
- *
- * 3) We walk all of the qgroups referenced by the root we are currently acting
- * on, and will either adjust old_refcnt in the case of a removal or the
- * new_refcnt in the case of an addition.
- *
- * 4) Finally we walk all the qgroups that are referenced by this range
- * including the root we are acting on currently.  We will adjust the counters
- * based on the number of roots we had and will have after this operation.
+ * 2) We have oper->old_roots and oper->new_roots, indicating the roots
+ * referring the extent before/after the delayed operation.
+ * So just update old/new_refcnt if one root is in old/new_roots.
  *
- * Take this example as an illustration
+ * 3) When updating one root in old/new_roots, we also needs to update all its
+ * parents.
  *
  *			[qgroup 1/0]
  *		     /         |          \
@@ -1856,36 +1914,41 @@ static int check_existing_refs(struct btrfs_trans_handle *trans,
  *		   \          |            /
  *		  [	   extent	    ]
  *
- * Say we are adding a reference that is covered by qg 0/0.  The first step
- * would give a refcnt of 1 to qg 0/1 and 0/2 and a refcnt of 2 to qg 1/0 with
- * old_roots being 2.  Because it is adding new_roots will be 1.  We then go
- * through qg 0/0 which will get the new_refcnt set to 1 and add 1 to qg 1/0's
- * new_refcnt, bringing it to 3.  We then walk through all of the qgroups, we
- * notice that the old refcnt for qg 0/0 < the new refcnt, so we added a
- * reference and thus must add the size to the referenced bytes.  Everything
- * else is the same so nothing else changes.
+ * Say we are adding a reference that is newly covered by qg 0/0.
+ * What we have in oper->old/new_roots:
+ * oper->old_roots = {0/1, 0/2}, nnodes = 2
+ * oper->new_roots = {0/0, 0/1, 0/2}, nnodes = 3
+ *
+ * Old refcnt update:
+ * 1) qg 0/1: 0->1, qg 1/0: 0->1  2)qg 0/2: 0->1, qg 1/0: 1->2
+ *
+ * New refcnt update:
+ * 1) qg 0/0: 0->1, qg 1/0: 0->1  2)qg 0/1: 0->1, qg 1/0: 1->2
+ * 3) qg 0/2: 0->1, qg 1/0: 2->3
+ *
+ * Accounting update:
+ * 1) qg 0/0, old 0, new 1, old_roots 2, new_roots 3.
+ * new > old, add rfer. new < new_roots, no add excl.
+ *
+ * 2) qg 0/1 ~ 0/2 , old 1, new 1, old_roots 2, new_roots 3.
+ * new == old, no add rfer. new < new_roots, no add excl.
+ *
+ * 3) qg 1/0, old 2, new 3, old_roots 2, new_roots 3.
+ * new > old, add rfer. new == new_roots, add excl
+ *
+ * See full judgements in qgroup_adjust_counters().
  */
 static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 				    struct btrfs_fs_info *fs_info,
 				    struct btrfs_qgroup_operation *oper)
 {
-	struct ulist *roots = NULL;
 	struct ulist *qgroups, *tmp;
 	struct btrfs_qgroup *qgroup;
-	struct seq_list elem = {};
 	u64 seq;
-	int old_roots = 0;
-	int new_roots = 0;
+	u64 old_roots = 0;
+	u64 new_roots = oper->new_roots->nnodes;
 	int ret = 0;
 
-	if (oper->elem.seq) {
-		ret = check_existing_refs(trans, fs_info, oper);
-		if (ret < 0)
-			return ret;
-		if (ret)
-			return 0;
-	}
-
 	qgroups = ulist_alloc(GFP_NOFS);
 	if (!qgroups)
 		return -ENOMEM;
@@ -1896,15 +1959,6 @@ static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 		return -ENOMEM;
 	}
 
-	btrfs_get_tree_mod_seq(fs_info, &elem);
-	ret = btrfs_find_all_roots(trans, fs_info, NULL, oper->bytenr, elem.seq,
-				   &roots, 0);
-	btrfs_put_tree_mod_seq(fs_info, &elem);
-	if (ret < 0) {
-		ulist_free(qgroups);
-		ulist_free(tmp);
-		return ret;
-	}
 	spin_lock(&fs_info->qgroup_lock);
 	qgroup = find_qgroup_rb(fs_info, oper->ref_root);
 	if (!qgroup)
@@ -1912,71 +1966,38 @@ static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
 	seq = fs_info->qgroup_seq;
 
 	/*
-	 * So roots is the list of all the roots currently pointing at the
-	 * bytenr, including the ref we are adding if we are adding, or not if
-	 * we are removing a ref.  So we pass in the ref_root to skip that root
-	 * in our calculations.  We set old_refnct and new_refcnt cause who the
-	 * hell knows what everything looked like before, and it doesn't matter
-	 * except...
-	 */
-	ret = qgroup_calc_old_refcnt(fs_info, oper->ref_root, tmp, roots, qgroups,
-				     seq, &old_roots, 0);
-	if (ret < 0)
-		goto out;
-
-	/*
-	 * Now adjust the refcounts of the qgroups that care about this
-	 * reference, either the old_count in the case of removal or new_count
-	 * in the case of an addition.
+	 * Update old refcnts, since we have oper->old_roots, just use them
 	 */
-	ret = qgroup_calc_new_refcnt(fs_info, oper, qgroup, tmp, qgroups,
-				     seq);
+	ret = qgroup_update_refcnt(fs_info, oper->old_roots, tmp, qgroups, seq,
+				   UPDATE_OLD);
 	if (ret < 0)
 		goto out;
 
 	/*
-	 * ...in the case of removals.  If we had a removal before we got around
-	 * to processing this operation then we need to find that guy and count
-	 * his references as if they really existed so we don't end up screwing
-	 * up the exclusive counts.  Then whenever we go to process the delete
-	 * everything will be grand and we can account for whatever exclusive
-	 * changes need to be made there.  We also have to pass in old_roots so
-	 * we have an accurate count of the roots as it pertains to this
-	 * operations view of the world.
+	 * Update new refcnts, since we have oper->new_roots, just use them
 	 */
-	ret = qgroup_account_deleted_refs(fs_info, oper, tmp, qgroups, seq,
-					  &old_roots);
+	ret = qgroup_update_refcnt(fs_info, oper->new_roots, tmp, qgroups, seq,
+				   UPDATE_NEW);
 	if (ret < 0)
 		goto out;
 
-	/*
-	 * We are adding our root, need to adjust up the number of roots,
-	 * otherwise old_roots is the number of roots we want.
-	 */
-	if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED) {
-		new_roots = old_roots + 1;
-	} else {
-		new_roots = old_roots;
-		old_roots++;
-	}
-
+	if (oper->old_roots)
+		old_roots = oper->old_roots->nnodes;
 	/*
 	 * Bump qgroup_seq to avoid seq overlap
 	 * XXX: This makes qgroup_seq mismatch with oper->seq.
 	 */
-	fs_info->qgroup_seq += old_roots + 1;
-
+	fs_info->qgroup_seq += max(old_roots, new_roots) + 1;
 
 	/*
 	 * And now the magic happens, bless Arne for having a pretty elegant
 	 * solution for this.
 	 */
-	qgroup_adjust_counters(fs_info, oper->ref_root, oper->num_bytes,
-			       qgroups, seq, old_roots, new_roots, 0);
+	qgroup_adjust_counters(fs_info, qgroups, oper->old_roots,
+			       oper->new_roots, oper->num_bytes, seq);
 out:
 	spin_unlock(&fs_info->qgroup_lock);
 	ulist_free(qgroups);
-	ulist_free(roots);
 	ulist_free(tmp);
 	return ret;
 }
@@ -2559,7 +2580,6 @@ qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
 	struct seq_list tree_mod_seq_elem = {};
 	u64 num_bytes;
 	u64 seq;
-	int new_roots;
 	int slot;
 	int ret;
 
@@ -2618,17 +2638,17 @@ qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
 		seq = fs_info->qgroup_seq;
 		fs_info->qgroup_seq += roots->nnodes + 1; /* max refcnt */
 
-		new_roots = 0;
-		ret = qgroup_calc_old_refcnt(fs_info, 0, tmp, roots, qgroups,
-					     seq, &new_roots, 1);
+		/* For rescan, we only need to update new refcnt */
+		ret = qgroup_update_refcnt(fs_info, roots, tmp, qgroups, seq,
+					   UPDATE_NEW);
 		if (ret < 0) {
 			spin_unlock(&fs_info->qgroup_lock);
 			ulist_free(roots);
 			goto out;
 		}
 
-		ret = qgroup_adjust_counters(fs_info, 0, num_bytes, qgroups,
-					     seq, 0, new_roots, 1);
+		ret = qgroup_adjust_counters(fs_info, qgroups, NULL, roots,
+					     num_bytes, seq);
 		if (ret < 0) {
 			spin_unlock(&fs_info->qgroup_lock);
 			ulist_free(roots);
-- 
2.3.3

[RFC PATCH 10/11] btrfs: qgroup-tests: Add old_roots ulist to allow qgroup test pass.

[Qu Wenruo]

Since new qgroup design need to get old_roots before calling
btrfs_qgroup_record_ref(), modify qgroup test to follow the new routine.

And of course, without this modification, it won't pass the qgroup
multi-ref test.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/backref.c            | 10 ++++++++++
 fs/btrfs/tests/qgroup-tests.c | 32 +++++++++++++++++++++++++++-----
 2 files changed, 37 insertions(+), 5 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index e33a003..58d87ab 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -1017,7 +1017,17 @@ again:
 	if (ret)
 		goto out;
 
+	/*
+	 * For sanity tests, all parents are 0, causing different roots
+	 * referring to one extent merged into one root.
+	 * So skip such search in sanity tests
+	 */
+#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
+	if (!trans || (trans && likely(trans->type != __TRANS_DUMMY)))
+		__merge_refs(&prefs, 2);
+#else
 	__merge_refs(&prefs, 2);
+#endif
 
 	while (!list_empty(&prefs)) {
 		ref = list_first_entry(&prefs, struct __prelim_ref, list);
diff --git a/fs/btrfs/tests/qgroup-tests.c b/fs/btrfs/tests/qgroup-tests.c
index c97c5f8..967a185 100644
--- a/fs/btrfs/tests/qgroup-tests.c
+++ b/fs/btrfs/tests/qgroup-tests.c
@@ -21,6 +21,7 @@
 #include "../transaction.h"
 #include "../disk-io.h"
 #include "../qgroup.h"
+#include "../backref.h"
 
 static void init_dummy_trans(struct btrfs_trans_handle *trans)
 {
@@ -294,6 +295,7 @@ static int test_multiple_refs(struct btrfs_root *root)
 {
 	struct btrfs_trans_handle trans;
 	struct btrfs_fs_info *fs_info = root->fs_info;
+	struct ulist *old_roots = NULL;
 	int ret;
 
 	init_dummy_trans(&trans);
@@ -329,16 +331,27 @@ static int test_multiple_refs(struct btrfs_root *root)
 		return -EINVAL;
 	}
 
+	/* Get correct old ref counts before writing tree backref */
+	ret = btrfs_find_all_roots(&trans, fs_info, NULL, 4096, 0, &old_roots, 1);
+	if (ret < 0) {
+		ulist_free(old_roots);
+		return ret;
+	}
+
 	ret = add_tree_ref(root, 4096, 4096, 0, 256);
-	if (ret)
+	if (ret) {
+		ulist_free(old_roots);
 		return ret;
+	}
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 256, 4096, 4096, 0,
-				      BTRFS_QGROUP_OPER_ADD_SHARED, 0);
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, old_roots, 256, 4096,
+				      4096, 0, BTRFS_QGROUP_OPER_ADD_SHARED, 0);
 	if (ret) {
 		test_msg("Qgroup record ref failed %d\n", ret);
+		ulist_free(old_roots);
 		return ret;
 	}
+	old_roots = NULL;
 
 	ret = btrfs_delayed_qgroup_accounting(&trans, fs_info);
 	if (ret) {
@@ -356,16 +369,25 @@ static int test_multiple_refs(struct btrfs_root *root)
 		return -EINVAL;
 	}
 
+	/* Get correct old ref counts before writing tree backref */
+	ret = btrfs_find_all_roots(&trans, fs_info, NULL, 4096, 0, &old_roots, 1);
+	if (ret < 0) {
+		ulist_free(old_roots);
+		return ret;
+	}
+
 	ret = remove_extent_ref(root, 4096, 4096, 0, 256);
 	if (ret)
 		return ret;
 
-	ret = btrfs_qgroup_record_ref(&trans, fs_info, NULL, 256, 4096, 4096, 0,
-				      BTRFS_QGROUP_OPER_SUB_SHARED, 0);
+	ret = btrfs_qgroup_record_ref(&trans, fs_info, old_roots, 256, 4096,
+				      4096, 0, BTRFS_QGROUP_OPER_SUB_SHARED, 0);
 	if (ret) {
+		ulist_free(old_roots);
 		test_msg("Qgroup record ref failed %d\n", ret);
 		return ret;
 	}
+	old_roots = NULL;
 
 	ret = btrfs_delayed_qgroup_accounting(&trans, fs_info);
 	if (ret) {
-- 
2.3.3

[RFC PATCH 11/11] btrfs: qgroup: Cleanup the unneeded codes.

[Qu Wenruo]

Cleanup the unneeded codes only for special cases.
Since the new, more generic but simpler codes are already here, use
them.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
It feels so good just pressing 'd' in vim!!!
---
 fs/btrfs/qgroup.c | 249 ------------------------------------------------------
 1 file changed, 249 deletions(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 16240e6..88abd13 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1564,222 +1564,6 @@ static int qgroup_update_refcnt(struct btrfs_fs_info *fs_info,
 	return 0;
 }
 
-static int qgroup_calc_old_refcnt(struct btrfs_fs_info *fs_info,
-				  u64 root_to_skip, struct ulist *tmp,
-				  struct ulist *roots, struct ulist *qgroups,
-				  u64 seq, int *old_roots, int rescan)
-{
-	struct ulist_node *unode;
-	struct ulist_iterator uiter;
-	struct ulist_node *tmp_unode;
-	struct ulist_iterator tmp_uiter;
-	struct btrfs_qgroup *qg;
-	int ret;
-
-	ULIST_ITER_INIT(&uiter);
-	while ((unode = ulist_next(roots, &uiter))) {
-		/* We don't count our current root here */
-		if (unode->val == root_to_skip)
-			continue;
-		qg = find_qgroup_rb(fs_info, unode->val);
-		if (!qg)
-			continue;
-		/*
-		 * We could have a pending removal of this same ref so we may
-		 * not have actually found our ref root when doing
-		 * btrfs_find_all_roots, so we need to keep track of how many
-		 * old roots we find in case we removed ours and added a
-		 * different one at the same time.  I don't think this could
-		 * happen in practice but that sort of thinking leads to pain
-		 * and suffering and to the dark side.
-		 */
-		(*old_roots)++;
-
-		ulist_reinit(tmp);
-		ret = ulist_add(qgroups, qg->qgroupid, ptr_to_u64(qg),
-				GFP_ATOMIC);
-		if (ret < 0)
-			return ret;
-		ret = ulist_add(tmp, qg->qgroupid, ptr_to_u64(qg), GFP_ATOMIC);
-		if (ret < 0)
-			return ret;
-		ULIST_ITER_INIT(&tmp_uiter);
-		while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
-			struct btrfs_qgroup_list *glist;
-			int mod;
-
-			qg = u64_to_ptr(tmp_unode->aux);
-			/*
-			 * We use this sequence number to keep from having to
-			 * run the whole list and 0 out the refcnt every time.
-			 * We basically use sequnce as the known 0 count and
-			 * then add 1 everytime we see a qgroup.  This is how we
-			 * get how many of the roots actually point up to the
-			 * upper level qgroups in order to determine exclusive
-			 * counts.
-			 *
-			 * For rescan none of the extent is recorded before so
-			 * we just don't add old_refcnt.
-			 */
-			if (rescan)
-				mod = 0;
-			else
-				mod = 1;
-			btrfs_qgroup_update_old_refcnt(qg, seq, mod);
-			btrfs_qgroup_update_new_refcnt(qg, seq, 1);
-			list_for_each_entry(glist, &qg->groups, next_group) {
-				ret = ulist_add(qgroups, glist->group->qgroupid,
-						ptr_to_u64(glist->group),
-						GFP_ATOMIC);
-				if (ret < 0)
-					return ret;
-				ret = ulist_add(tmp, glist->group->qgroupid,
-						ptr_to_u64(glist->group),
-						GFP_ATOMIC);
-				if (ret < 0)
-					return ret;
-			}
-		}
-	}
-	return 0;
-}
-
-/*
- * We need to walk forward in our operation tree and account for any roots that
- * were deleted after we made this operation.
- */
-static int qgroup_account_deleted_refs(struct btrfs_fs_info *fs_info,
-				       struct btrfs_qgroup_operation *oper,
-				       struct ulist *tmp,
-				       struct ulist *qgroups, u64 seq,
-				       int *old_roots)
-{
-	struct ulist_node *unode;
-	struct ulist_iterator uiter;
-	struct btrfs_qgroup *qg;
-	struct btrfs_qgroup_operation *tmp_oper;
-	struct rb_node *n;
-	int ret;
-
-	ulist_reinit(tmp);
-
-	/*
-	 * We only walk forward in the tree since we're only interested in
-	 * removals that happened _after_  our operation.
-	 */
-	spin_lock(&fs_info->qgroup_op_lock);
-	n = rb_next(&oper->n);
-	spin_unlock(&fs_info->qgroup_op_lock);
-	if (!n)
-		return 0;
-	tmp_oper = rb_entry(n, struct btrfs_qgroup_operation, n);
-	while (tmp_oper->bytenr == oper->bytenr) {
-		/*
-		 * If it's not a removal we don't care, additions work out
-		 * properly with our refcnt tracking.
-		 */
-		if (tmp_oper->type != BTRFS_QGROUP_OPER_SUB_SHARED &&
-		    tmp_oper->type != BTRFS_QGROUP_OPER_SUB_EXCL)
-			goto next;
-		qg = find_qgroup_rb(fs_info, tmp_oper->ref_root);
-		if (!qg)
-			goto next;
-		ret = ulist_add(qgroups, qg->qgroupid, ptr_to_u64(qg),
-				GFP_ATOMIC);
-		if (ret) {
-			if (ret < 0)
-				return ret;
-			/*
-			 * We only want to increase old_roots if this qgroup is
-			 * not already in the list of qgroups.  If it is already
-			 * there then that means it must have been re-added or
-			 * the delete will be discarded because we had an
-			 * existing ref that we haven't looked up yet.  In this
-			 * case we don't want to increase old_roots.  So if ret
-			 * == 1 then we know that this is the first time we've
-			 * seen this qgroup and we can bump the old_roots.
-			 */
-			(*old_roots)++;
-			ret = ulist_add(tmp, qg->qgroupid, ptr_to_u64(qg),
-					GFP_ATOMIC);
-			if (ret < 0)
-				return ret;
-		}
-next:
-		spin_lock(&fs_info->qgroup_op_lock);
-		n = rb_next(&tmp_oper->n);
-		spin_unlock(&fs_info->qgroup_op_lock);
-		if (!n)
-			break;
-		tmp_oper = rb_entry(n, struct btrfs_qgroup_operation, n);
-	}
-
-	/* Ok now process the qgroups we found */
-	ULIST_ITER_INIT(&uiter);
-	while ((unode = ulist_next(tmp, &uiter))) {
-		struct btrfs_qgroup_list *glist;
-
-		qg = u64_to_ptr(unode->aux);
-		btrfs_qgroup_update_old_refcnt(qg, seq, 1);
-		btrfs_qgroup_update_new_refcnt(qg, seq, 1);
-		list_for_each_entry(glist, &qg->groups, next_group) {
-			ret = ulist_add(qgroups, glist->group->qgroupid,
-					ptr_to_u64(glist->group), GFP_ATOMIC);
-			if (ret < 0)
-				return ret;
-			ret = ulist_add(tmp, glist->group->qgroupid,
-					ptr_to_u64(glist->group), GFP_ATOMIC);
-			if (ret < 0)
-				return ret;
-		}
-	}
-	return 0;
-}
-
-/* Add refcnt for the newly added reference. */
-static int qgroup_calc_new_refcnt(struct btrfs_fs_info *fs_info,
-				  struct btrfs_qgroup_operation *oper,
-				  struct btrfs_qgroup *qgroup,
-				  struct ulist *tmp, struct ulist *qgroups,
-				  u64 seq)
-{
-	struct ulist_node *unode;
-	struct ulist_iterator uiter;
-	struct btrfs_qgroup *qg;
-	int ret;
-
-	ulist_reinit(tmp);
-	ret = ulist_add(qgroups, qgroup->qgroupid, ptr_to_u64(qgroup),
-			GFP_ATOMIC);
-	if (ret < 0)
-		return ret;
-	ret = ulist_add(tmp, qgroup->qgroupid, ptr_to_u64(qgroup),
-			GFP_ATOMIC);
-	if (ret < 0)
-		return ret;
-	ULIST_ITER_INIT(&uiter);
-	while ((unode = ulist_next(tmp, &uiter))) {
-		struct btrfs_qgroup_list *glist;
-
-		qg = u64_to_ptr(unode->aux);
-		if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED)
-			btrfs_qgroup_update_new_refcnt(qg, seq, 1);
-		else
-			btrfs_qgroup_update_old_refcnt(qg, seq, 1);
-		list_for_each_entry(glist, &qg->groups, next_group) {
-			ret = ulist_add(tmp, glist->group->qgroupid,
-					ptr_to_u64(glist->group), GFP_ATOMIC);
-			if (ret < 0)
-				return ret;
-			ret = ulist_add(qgroups, glist->group->qgroupid,
-					ptr_to_u64(glist->group), GFP_ATOMIC);
-			if (ret < 0)
-				return ret;
-		}
-	}
-	return 0;
-}
-
 /*
  * This adjusts the counters for all referenced qgroups if need be.
  */
@@ -1858,39 +1642,6 @@ static int qgroup_adjust_counters(struct btrfs_fs_info *fs_info,
 }
 
 /*
- * If we removed a data extent and there were other references for that bytenr
- * then we need to lookup all referenced roots to make sure we still don't
- * reference this bytenr.  If we do then we can just discard this operation.
- */
-static int check_existing_refs(struct btrfs_trans_handle *trans,
-			       struct btrfs_fs_info *fs_info,
-			       struct btrfs_qgroup_operation *oper)
-{
-	struct ulist *roots = NULL;
-	struct ulist_node *unode;
-	struct ulist_iterator uiter;
-	int ret = 0;
-
-	ret = btrfs_find_all_roots(trans, fs_info, NULL, oper->bytenr,
-				   oper->elem.seq, &roots, 0);
-	if (ret < 0)
-		return ret;
-	ret = 0;
-
-	ULIST_ITER_INIT(&uiter);
-	while ((unode = ulist_next(roots, &uiter))) {
-		if (unode->val == oper->ref_root) {
-			ret = 1;
-			break;
-		}
-	}
-	ulist_free(roots);
-	btrfs_put_tree_mod_seq(fs_info, &oper->elem);
-
-	return ret;
-}
-
-/*
  * If we share a reference across multiple roots then we may need to adjust
  * various qgroups referenced and exclusive counters.  The basic premise is this
  *
-- 
2.3.3