[PATCH 36/40] btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified node

[Qu Wenruo <wqu@suse.com>]

Introduce a new static function, iterate_all_roots(), to find all
roots for specified backref node.

This function will do iterative depth-first search, and queue hit root
objectid to the result ulist.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/qgroup.c | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 1493f771e986..063397af2a1a 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -1765,6 +1765,46 @@ static struct btrfs_backref_node *qgroup_backref_cache_build(
 	return node;
 }
 
+/* Iterate all roots in the backref_cache, and add root objectid into @roots */
+static int iterate_all_roots(struct btrfs_backref_node *node,
+			     struct ulist *roots)
+{
+	struct btrfs_backref_edge *edge;
+	struct btrfs_backref_node *upper;
+	int ret = 0;
+
+	ASSERT(node->level < BTRFS_MAX_LEVEL);
+
+	/* Useless node, exit directly */
+	if (node->detached || node->is_reloc_root || node->cowonly)
+		goto out;
+
+	/* Find a root, queue to @roots ulist */
+	if (list_empty(&node->upper)) {
+		ASSERT(is_fstree(node->owner));
+		ret = ulist_add(roots, node->owner, 0, GFP_NOFS);
+		goto out;
+	}
+
+	/* Go upper level */
+	list_for_each_entry(edge, &node->upper, list[LOWER]) {
+		upper = edge->node[UPPER];
+
+		if (upper->level != node->level + 1 ||
+		    upper->level >= BTRFS_MAX_LEVEL) {
+			ret = -EUCLEAN;
+			goto out;
+		}
+		ret = iterate_all_roots(upper, roots);
+		if (ret < 0)
+			goto out;
+	}
+out:
+	if (ret < 0)
+		ulist_release(roots);
+	return ret;
+}
+
 int btrfs_qgroup_trace_extent_post(struct btrfs_fs_info *fs_info,
 				   struct btrfs_qgroup_extent_record *qrecord)
 {
-- 
2.25.2