[PATCH] qgraph: implement stack as a linked list

[PATCH] qgraph: implement stack as a linked list

[Paolo Bonzini]

The stack used to visit the graph is implemented as a fixed-size array,
and the array is sized according to the maximum anticipated length of
a path on the graph.  However, the worst case for a depth-first search
is to push all nodes on the graph, and in fact stack overflows have
been observed in the past depending on the ordering of the constructors.

To fix the problem once and for all, use a QSLIST instead of the array,
allocating QOSStackElements from the heap.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 tests/qtest/libqos/qgraph.c | 35 +++++++++++------------------------
 1 file changed, 11 insertions(+), 24 deletions(-)

diff --git a/tests/qtest/libqos/qgraph.c b/tests/qtest/libqos/qgraph.c
index 0a2dddfafa..2433e6ea4b 100644
--- a/tests/qtest/libqos/qgraph.c
+++ b/tests/qtest/libqos/qgraph.c
@@ -52,6 +52,7 @@ struct QOSStackElement {
     QOSStackElement *parent;
     QOSGraphEdge *parent_edge;
     int length;
+    QSLIST_ENTRY(QOSStackElement) next;
 };
 
 /* Each enty in these hash table will consist of <string, node/edge> pair. */
@@ -59,8 +60,7 @@ static GHashTable *edge_table;
 static GHashTable *node_table;
 
 /* stack used by the DFS algorithm to store the path from machine to test */
-static QOSStackElement qos_node_stack[QOS_PATH_MAX_ELEMENT_SIZE];
-static int qos_node_tos;
+static QSLIST_HEAD(, QOSStackElement) qos_node_stack;
 
 /**
  * add_edge(): creates an edge of type @type
@@ -325,40 +325,27 @@ static void qos_print_cb(QOSGraphNode *path, int length)
 static void qos_push(QOSGraphNode *el, QOSStackElement *parent,
                      QOSGraphEdge *e)
 {
+    QOSStackElement *elem = g_new0(QOSStackElement, 1);
     int len = 0; /* root is not counted */
-    if (qos_node_tos == QOS_PATH_MAX_ELEMENT_SIZE) {
-        g_printerr("QOSStack: full stack, cannot push");
-        abort();
-    }
-
     if (parent) {
         len = parent->length + 1;
     }
-    qos_node_stack[qos_node_tos++] = (QOSStackElement) {
+    *elem = (QOSStackElement) {
         .node = el,
         .parent = parent,
         .parent_edge = e,
         .length = len,
     };
-}
-
-/* qos_tos(): returns the top of stack, without popping */
-static QOSStackElement *qos_tos(void)
-{
-    return &qos_node_stack[qos_node_tos - 1];
+    QSLIST_INSERT_HEAD(qos_node_stack, elem, next);
 }
 
 /* qos_pop(): pops an element from the tos, setting it unvisited*/
-static QOSStackElement *qos_pop(void)
+static void qos_pop(void)
 {
-    if (qos_node_tos == 0) {
-        g_printerr("QOSStack: empty stack, cannot pop");
-        abort();
-    }
-    QOSStackElement *e = qos_tos();
+    QOSStackElement *e = QSLIST_FIRST(qos_node_stack);
     e->node->visited = false;
-    qos_node_tos--;
-    return e;
+    QSLIST_REMOVE_HEAD(qos_node_stack, next);
+    g_free(e);
 }
 
 /**
@@ -400,8 +387,8 @@ static void qos_traverse_graph(QOSGraphNode *root, QOSTestCallback callback)
 
     qos_push(root, NULL, NULL);
 
-    while (qos_node_tos > 0) {
-        s_el = qos_tos();
+    while (!QSLIST_EMPTY(qos_node_stack)) {
+        s_el = QSLIST_HEAD(qos_node_stack);
         v = s_el->node;
         if (v->visited) {
             qos_pop();
-- 
2.37.3

Re: [PATCH] qgraph: implement stack as a linked list

[Richard Henderson]

On 10/11/22 03:46, Paolo Bonzini wrote:
>   {
> +    QOSStackElement *elem = g_new0(QOSStackElement, 1);
>       int len = 0; /* root is not counted */
> -    if (qos_node_tos == QOS_PATH_MAX_ELEMENT_SIZE) {
> -        g_printerr("QOSStack: full stack, cannot push");
> -        abort();
> -    }
> -
>       if (parent) {
>           len = parent->length + 1;
>       }
> -    qos_node_stack[qos_node_tos++] = (QOSStackElement) {
> +    *elem = (QOSStackElement) {
>           .node = el,
>           .parent = parent,
>           .parent_edge = e,
>           .length = len,
>       };
> -}

If you're going to completely initialize the structure via assignment, you don't need to 
zero the storage first.  I suggest either g_new + structure assignment or g_new0 + 
sequence of element assignments.

Otherwise,
Reviewed-by: Richard Henderson <richard.henderson@linaro.org>


r~

[PATCH] qgraph: implement stack as a linked list

[Paolo Bonzini]

The stack used to visit the graph is implemented as a fixed-size array,
and the array is sized according to the maximum anticipated length of
a path on the graph.  However, the worst case for a depth-first search
is to push all nodes on the graph, and in fact stack overflows have
been observed in the past depending on the ordering of the constructors.

To fix the problem once and for all, use a QSLIST instead of the array,
allocating QOSStackElements from the heap.

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 tests/qtest/libqos/qgraph.c | 35 +++++++++++------------------------
 1 file changed, 11 insertions(+), 24 deletions(-)

diff --git a/tests/qtest/libqos/qgraph.c b/tests/qtest/libqos/qgraph.c
index 0a2dddfafa..ff9d389f12 100644
--- a/tests/qtest/libqos/qgraph.c
+++ b/tests/qtest/libqos/qgraph.c
@@ -52,6 +52,7 @@ struct QOSStackElement {
     QOSStackElement *parent;
     QOSGraphEdge *parent_edge;
     int length;
+    QSLIST_ENTRY(QOSStackElement) next;
 };
 
 /* Each enty in these hash table will consist of <string, node/edge> pair. */
@@ -59,8 +60,7 @@ static GHashTable *edge_table;
 static GHashTable *node_table;
 
 /* stack used by the DFS algorithm to store the path from machine to test */
-static QOSStackElement qos_node_stack[QOS_PATH_MAX_ELEMENT_SIZE];
-static int qos_node_tos;
+static QSLIST_HEAD(, QOSStackElement) qos_node_stack;
 
 /**
  * add_edge(): creates an edge of type @type
@@ -325,40 +325,27 @@ static void qos_print_cb(QOSGraphNode *path, int length)
 static void qos_push(QOSGraphNode *el, QOSStackElement *parent,
                      QOSGraphEdge *e)
 {
+    QOSStackElement *elem = g_new(QOSStackElement, 1);
     int len = 0; /* root is not counted */
-    if (qos_node_tos == QOS_PATH_MAX_ELEMENT_SIZE) {
-        g_printerr("QOSStack: full stack, cannot push");
-        abort();
-    }
-
     if (parent) {
         len = parent->length + 1;
     }
-    qos_node_stack[qos_node_tos++] = (QOSStackElement) {
+    *elem = (QOSStackElement) {
         .node = el,
         .parent = parent,
         .parent_edge = e,
         .length = len,
     };
-}
-
-/* qos_tos(): returns the top of stack, without popping */
-static QOSStackElement *qos_tos(void)
-{
-    return &qos_node_stack[qos_node_tos - 1];
+    QSLIST_INSERT_HEAD(qos_node_stack, elem, next);
 }
 
 /* qos_pop(): pops an element from the tos, setting it unvisited*/
-static QOSStackElement *qos_pop(void)
+static void qos_pop(void)
 {
-    if (qos_node_tos == 0) {
-        g_printerr("QOSStack: empty stack, cannot pop");
-        abort();
-    }
-    QOSStackElement *e = qos_tos();
+    QOSStackElement *e = QSLIST_FIRST(qos_node_stack);
     e->node->visited = false;
-    qos_node_tos--;
-    return e;
+    QSLIST_REMOVE_HEAD(qos_node_stack, next);
+    g_free(e);
 }
 
 /**
@@ -400,8 +387,8 @@ static void qos_traverse_graph(QOSGraphNode *root, QOSTestCallback callback)
 
     qos_push(root, NULL, NULL);
 
-    while (qos_node_tos > 0) {
-        s_el = qos_tos();
+    while (!QSLIST_EMPTY(qos_node_stack)) {
+        s_el = QSLIST_HEAD(qos_node_stack);
         v = s_el->node;
         if (v->visited) {
             qos_pop();
-- 
2.37.3