From 5d0050c8bfa3e3b9b9b8a90a4b7251d978639288 Mon Sep 17 00:00:00 2001
From: Eric Anholt <eric@anholt.net>
Date: Tue, 8 Sep 2020 14:25:42 -0700
Subject: [PATCH] util/dag: Add a validation function.

I experienced a circular dag in freedreno, and wanted a way to see what
was going wrong.

Reviewed-by: Rob Clark <robdclark@chromium.org>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/6656>
---
 src/util/dag.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/util/dag.h |  2 ++
 2 files changed, 68 insertions(+)

diff --git a/src/util/dag.c b/src/util/dag.c
index 841d8cf..ab80795 100644
--- a/src/util/dag.c
+++ b/src/util/dag.c
@@ -23,6 +23,7 @@
 
 #include "util/set.h"
 #include "util/dag.h"
+#include <stdio.h>
 
 static void
 append_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data)
@@ -219,3 +220,68 @@ dag_create(void *mem_ctx)
    return dag;
 }
 
+struct dag_validate_state {
+   struct util_dynarray stack;
+   struct set *stack_set;
+   struct set *seen;
+   void (*cb)(const struct dag_node *node, void *data);
+   void *data;
+};
+
+static void
+dag_validate_node(struct dag_node *node,
+                  struct dag_validate_state *state)
+{
+   if (_mesa_set_search(state->stack_set, node)) {
+      fprintf(stderr, "DAG validation failed at:\n");
+      fprintf(stderr, "  %p: ", node);
+      state->cb(node, state->data);
+      fprintf(stderr, "\n");
+      fprintf(stderr, "Nodes in stack:\n");
+      util_dynarray_foreach(&state->stack, struct dag_node *, nodep) {
+         struct dag_node *node = *nodep;
+         fprintf(stderr, "  %p: ", node);
+         state->cb(node, state->data);
+         fprintf(stderr, "\n");
+      }
+      abort();
+   }
+
+   if (_mesa_set_search(state->seen, node))
+      return;
+
+   _mesa_set_add(state->stack_set, node);
+   _mesa_set_add(state->seen, node);
+   util_dynarray_append(&state->stack, struct dag_node *, node);
+
+   util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
+      dag_validate_node(edge->child, state);
+   }
+
+   (void)util_dynarray_pop(&state->stack, struct dag_node *);
+   _mesa_set_remove_key(state->stack_set, node);
+}
+
+void
+dag_validate(struct dag *dag, void (*cb)(const struct dag_node *node,
+                                         void *data),
+             void *data)
+{
+   void *mem_ctx = ralloc_context(NULL);
+   struct dag_validate_state state = {
+      .stack_set = _mesa_pointer_set_create(mem_ctx),
+      .seen = _mesa_pointer_set_create(mem_ctx),
+      .cb = cb,
+      .data = data,
+   };
+
+   util_dynarray_init(&state.stack, mem_ctx);
+
+   list_validate(&dag->heads);
+
+   list_for_each_entry(struct dag_node, node, &dag->heads, link) {
+      dag_validate_node(node, &state);
+   }
+
+   ralloc_free(mem_ctx);
+}
diff --git a/src/util/dag.h b/src/util/dag.h
index 3ede13d..a8a41ff 100644
--- a/src/util/dag.h
+++ b/src/util/dag.h
@@ -58,6 +58,8 @@ void dag_remove_edge(struct dag *dag, struct dag_edge *edge);
 void dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
                                                         void *data), void *data);
 void dag_prune_head(struct dag *dag, struct dag_node *node);
+void dag_validate(struct dag *dag, void (*cb)(const struct dag_node *node,
+                                              void *data), void *data);
 
 #ifdef __cplusplus
 }
-- 
2.7.4