tools/xenstore: add generic treewalk function

Add a generic function to walk the complete node tree. It will start
at "/" and descend recursively into each child, calling a function
specified by the caller. Depending on the return value of the user
specified function the walk will be aborted, continued, or the current
child will be skipped by not descending into its children.

This is part of XSA-418 / CVE-2022-42321.

Signed-off-by: Juergen Gross <jgross@suse.com>
Acked-by: Julien Grall <jgrall@amazon.com>
(cherry picked from commit 0d7c5d19bc27492360196e7dad2b227908564fff)

2 files changed, 170 insertions, 13 deletions

diff --git a/tools/xenstore/xenstored_core.c b/tools/xenstore/xenstored_core.c
index cef9fc1c1e..47559a85d4 100644
--- a/tools/xenstore/xenstored_core.c
+++ b/tools/xenstore/xenstored_core.c
@@ -1733,6 +1733,135 @@ static int do_set_perms(const void *ctx, struct connection *conn,
 	return 0;
 }
 
+static char *child_name(const void *ctx, const char *s1, const char *s2)
+{
+	if (strcmp(s1, "/"))
+		return talloc_asprintf(ctx, "%s/%s", s1, s2);
+	return talloc_asprintf(ctx, "/%s", s2);
+}
+
+static int rm_from_parent(struct connection *conn, struct node *parent,
+			  const char *name)
+{
+	size_t off;
+
+	if (!parent)
+		return WALK_TREE_ERROR_STOP;
+
+	for (off = parent->childoff - 1; off && parent->children[off - 1];
+	     off--);
+	if (remove_child_entry(conn, parent, off)) {
+		log("treewalk: child entry could not be removed from '%s'",
+		    parent->name);
+		return WALK_TREE_ERROR_STOP;
+	}
+	parent->childoff = off;
+
+	return WALK_TREE_OK;
+}
+
+static int walk_call_func(const void *ctx, struct connection *conn,
+			  struct node *node, struct node *parent, void *arg,
+			  int (*func)(const void *ctx, struct connection *conn,
+				      struct node *node, void *arg))
+{
+	int ret;
+
+	if (!func)
+		return WALK_TREE_OK;
+
+	ret = func(ctx, conn, node, arg);
+	if (ret == WALK_TREE_RM_CHILDENTRY && parent)
+		ret = rm_from_parent(conn, parent, node->name);
+
+	return ret;
+}
+
+int walk_node_tree(const void *ctx, struct connection *conn, const char *root,
+		   struct walk_funcs *funcs, void *arg)
+{
+	int ret = 0;
+	void *tmpctx;
+	char *name;
+	struct node *node = NULL;
+	struct node *parent = NULL;
+
+	tmpctx = talloc_new(ctx);
+	if (!tmpctx) {
+		errno = ENOMEM;
+		return WALK_TREE_ERROR_STOP;
+	}
+	name = talloc_strdup(tmpctx, root);
+	if (!name) {
+		errno = ENOMEM;
+		talloc_free(tmpctx);
+		return WALK_TREE_ERROR_STOP;
+	}
+
+	/* Continue the walk until an error is returned. */
+	while (ret >= 0) {
+		/* node == NULL possible only for the initial loop iteration. */
+		if (node) {
+			/* Go one step up if ret or if last child finished. */
+			if (ret || node->childoff >= node->childlen) {
+				parent = node->parent;
+				/* Call function AFTER processing a node. */
+				ret = walk_call_func(ctx, conn, node, parent,
+						     arg, funcs->exit);
+				/* Last node, so exit loop. */
+				if (!parent)
+					break;
+				talloc_free(node);
+				/* Continue with parent. */
+				node = parent;
+				continue;
+			}
+			/* Get next child of current node. */
+			name = child_name(tmpctx, node->name,
+					  node->children + node->childoff);
+			if (!name) {
+				ret = WALK_TREE_ERROR_STOP;
+				break;
+			}
+			/* Point to next child. */
+			node->childoff += strlen(node->children +
+						 node->childoff) + 1;
+			/* Descent into children. */
+			parent = node;
+		}
+		/* Read next node (root node or next child). */
+		node = read_node(conn, tmpctx, name);
+		if (!node) {
+			/* Child not found - should not happen! */
+			/* ENOENT case can be handled by supplied function. */
+			if (errno == ENOENT && funcs->enoent)
+				ret = funcs->enoent(ctx, conn, parent, name,
+						    arg);
+			else
+				ret = WALK_TREE_ERROR_STOP;
+			if (!parent)
+				break;
+			if (ret == WALK_TREE_RM_CHILDENTRY)
+				ret = rm_from_parent(conn, parent, name);
+			if (ret < 0)
+				break;
+			talloc_free(name);
+			node = parent;
+			continue;
+		}
+		talloc_free(name);
+		node->parent = parent;
+		node->childoff = 0;
+		/* Call function BEFORE processing a node. */
+		ret = walk_call_func(ctx, conn, node, parent, arg,
+				     funcs->enter);
+	}
+
+	talloc_free(tmpctx);
+
+	return ret < 0 ? ret : WALK_TREE_OK;
+}
+
 static struct {
 	const char *str;
 	int (*func)(const void *ctx, struct connection *conn,
@@ -2105,18 +2234,6 @@ static int keys_equal_fn(void *key1, void *key2)
 	return 0 == strcmp((char *)key1, (char *)key2);
 }
 
-
-static char *child_name(const char *s1, const char *s2)
-{
-	if (strcmp(s1, "/")) {
-		return talloc_asprintf(NULL, "%s/%s", s1, s2);
-	}
-	else {
-		return talloc_asprintf(NULL, "/%s", s2);
-	}
-}
-
-
 int remember_string(struct hashtable *hash, const char *str)
 {
 	char *k = malloc(strlen(str) + 1);
@@ -2172,7 +2289,7 @@ static int check_store_(const char *name, struct hashtable *reachable)
 		while (i < node->childlen && !ret) {
 			struct node *childnode;
 			size_t childlen = strlen(node->children + i);
-			char * childname = child_name(node->name,
+			char * childname = child_name(NULL, node->name,
 						      node->children + i);
 
 			if (!childname) {
diff --git a/tools/xenstore/xenstored_core.h b/tools/xenstore/xenstored_core.h
index 5abf06c21c..fc9882ac37 100644
--- a/tools/xenstore/xenstored_core.h
+++ b/tools/xenstore/xenstored_core.h
@@ -167,6 +167,7 @@ struct node {
 
 	/* Children, each nul-terminated. */
 	unsigned int childlen;
+	unsigned int childoff;	/* Used by walk_node_tree() internally. */
 	char *children;
 
 	/* Allocation information for node currently in store. */
@@ -278,6 +279,45 @@ int do_tdb_delete(struct connection *conn, TDB_DATA *key,
 
 void conn_free_buffered_data(struct connection *conn);
 
+/*
+ * Walk the node tree below root calling funcs->enter() and funcs->exit() for
+ * each node. funcs->enter() is being called when entering a node, so before
+ * any of the children of the node is processed. funcs->exit() is being
+ * called when leaving the node, so after all children have been processed.
+ * funcs->enoent() is being called when a node isn't existing.
+ * funcs->*() return values:
+ *  < 0: tree walk is stopped, walk_node_tree() returns funcs->*() return value
+ *       in case WALK_TREE_ERROR_STOP is returned, errno should be set
+ *  WALK_TREE_OK: tree walk is continuing
+ *  WALK_TREE_SKIP_CHILDREN: tree walk won't descend below current node, but
+ *       walk continues
+ *  WALK_TREE_RM_CHILDENTRY: Remove the child entry from its parent and write
+ *       the modified parent node back to the data base, implies to not descend
+ *       below the current node, but to continue the walk
+ * funcs->*() is allowed to modify the node it is called for in the data base.
+ * In case funcs->enter() is deleting the node, it must not return WALK_TREE_OK
+ * in order to avoid descending into no longer existing children.
+ */
+/* Return values for funcs->*() and walk_node_tree(). */
+#define WALK_TREE_SUCCESS_STOP  -100    /* Stop walk early, no error. */
+#define WALK_TREE_ERROR_STOP    -1      /* Stop walk due to error. */
+#define WALK_TREE_OK            0       /* No error. */
+/* Return value for funcs->*() only. */
+#define WALK_TREE_SKIP_CHILDREN 1       /* Don't recurse below current node. */
+#define WALK_TREE_RM_CHILDENTRY 2       /* Remove child entry from parent. */
+
+struct walk_funcs {
+	int (*enter)(const void *ctx, struct connection *conn,
+		     struct node *node, void *arg);
+	int (*exit)(const void *ctx, struct connection *conn,
+		    struct node *node, void *arg);
+	int (*enoent)(const void *ctx, struct connection *conn,
+		      struct node *parent, char *name, void *arg);
+};
+
+int walk_node_tree(const void *ctx, struct connection *conn, const char *root,
+		   struct walk_funcs *funcs, void *arg);
+
 #endif /* _XENSTORED_CORE_H */
 
 /*