tests: qgraph API for the qtest driver framework

Add qgraph API that allows to add/remove nodes and edges from the graph,
implementation of Depth First Search to discover the paths and basic unit
test to check correctness of the API.
Included also a main executable that takes care of starting the framework,
create the nodes, set the available drivers/machines, discover the path and
run tests.

graph.h provides the public API to manage the graph nodes/edges
graph_extra.h provides a more private API used successively by the gtest integration part
qos-test.c provides the main executable

Signed-off-by: Emanuele Giuseppe Esposito <e.emanuelegiuseppe@gmail.com>
[Paolo's changes compared to the Google Summer of Code submission:
 * added subprocess to test options
 * refactored object creation to support live migration tests
 * removed driver .before callback (unused)
 * removed test .after callbacks (replaced by GTest destruction queue)]
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

3 files changed, 1585 insertions, 0 deletions

diff --git a/tests/libqos/qgraph.c b/tests/libqos/qgraph.c
new file mode 100644
index 0000000000..122efc1b7b
--- /dev/null
+++ b/tests/libqos/qgraph.c
@@ -0,0 +1,753 @@
+/*
+ * libqos driver framework
+ *
+ * Copyright (c) 2018 Emanuele Giuseppe Esposito <e.emanuelegiuseppe@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2 as published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>
+ */
+
+#include "qemu/osdep.h"
+#include "libqtest.h"
+#include "qemu/queue.h"
+#include "libqos/qgraph_internal.h"
+#include "libqos/qgraph.h"
+
+#define QGRAPH_PRINT_DEBUG 0
+#define QOS_ROOT ""
+typedef struct QOSStackElement QOSStackElement;
+
+/* Graph Edge.*/
+struct QOSGraphEdge {
+    QOSEdgeType type;
+    char *dest;
+    void *arg;                /* just for QEDGE_CONTAINS
+                               * and QEDGE_CONSUMED_BY */
+    char *extra_device_opts;  /* added to -device option, "," is
+                               * automatically added
+                               */
+    char *before_cmd_line;    /* added before node cmd_line */
+    char *after_cmd_line;     /* added after -device options */
+    char *edge_name;          /* used by QEDGE_CONTAINS */
+    QSLIST_ENTRY(QOSGraphEdge) edge_list;
+};
+
+typedef QSLIST_HEAD(, QOSGraphEdge) QOSGraphEdgeList;
+
+/**
+ * Stack used to keep track of the discovered path when using
+ * the DFS algorithm
+ */
+struct QOSStackElement {
+    QOSGraphNode *node;
+    QOSStackElement *parent;
+    QOSGraphEdge *parent_edge;
+    int length;
+};
+
+/* Each enty in these hash table will consist of <string, node/edge> pair. */
+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;
+
+/**
+ * add_edge(): creates an edge of type @type
+ * from @source to @dest node, and inserts it in the
+ * edges hash table
+ *
+ * Nodes @source and @dest do not necessarily need to exist.
+ * Possibility to add also options (see #QOSGraphEdgeOptions)
+ * edge->edge_name is used as identifier for get_device relationships,
+ * so by default is equal to @dest.
+ */
+static void add_edge(const char *source, const char *dest,
+                     QOSEdgeType type, QOSGraphEdgeOptions *opts)
+{
+    char *key;
+    QOSGraphEdgeList *list = g_hash_table_lookup(edge_table, source);
+
+    if (!list) {
+        list = g_new0(QOSGraphEdgeList, 1);
+        key = g_strdup(source);
+        g_hash_table_insert(edge_table, key, list);
+    }
+
+    if (!opts) {
+        opts = &(QOSGraphEdgeOptions) { };
+    }
+
+    QOSGraphEdge *edge = g_new0(QOSGraphEdge, 1);
+    edge->type = type;
+    edge->dest = g_strdup(dest);
+    edge->edge_name = g_strdup(opts->edge_name ?: dest);
+    edge->arg = g_memdup(opts->arg, opts->size_arg);
+
+    edge->before_cmd_line =
+        opts->before_cmd_line ? g_strconcat(" ", opts->before_cmd_line, NULL) : NULL;
+    edge->extra_device_opts =
+        opts->extra_device_opts ? g_strconcat(",", opts->extra_device_opts, NULL) : NULL;
+    edge->after_cmd_line =
+        opts->after_cmd_line ? g_strconcat(" ", opts->after_cmd_line, NULL) : NULL;
+
+    QSLIST_INSERT_HEAD(list, edge, edge_list);
+}
+
+/* destroy_edges(): frees all edges inside a given @list */
+static void destroy_edges(void *list)
+{
+    QOSGraphEdge *temp;
+    QOSGraphEdgeList *elist = list;
+
+    while (!QSLIST_EMPTY(elist)) {
+        temp = QSLIST_FIRST(elist);
+        QSLIST_REMOVE_HEAD(elist, edge_list);
+        g_free(temp->dest);
+        g_free(temp->before_cmd_line);
+        g_free(temp->after_cmd_line);
+        g_free(temp->extra_device_opts);
+        g_free(temp->edge_name);
+        g_free(temp->arg);
+        g_free(temp);
+    }
+    g_free(elist);
+}
+
+/**
+ * create_node(): creates a node @name of type @type
+ * and inserts it to the nodes hash table.
+ * By default, node is not available.
+ */
+static QOSGraphNode *create_node(const char *name, QOSNodeType type)
+{
+    if (g_hash_table_lookup(node_table, name)) {
+        g_printerr("Node %s already created\n", name);
+        abort();
+    }
+
+    QOSGraphNode *node = g_new0(QOSGraphNode, 1);
+    node->type = type;
+    node->available = false;
+    node->name = g_strdup(name);
+    g_hash_table_insert(node_table, node->name, node);
+    return node;
+}
+
+/**
+ * destroy_node(): frees a node @val from the nodes hash table.
+ * Note that node->name is not free'd since it will represent the
+ * hash table key
+ */
+static void destroy_node(void *val)
+{
+    QOSGraphNode *node = val;
+    g_free(node->command_line);
+    g_free(node);
+}
+
+/**
+ * destroy_string(): frees @key from the nodes hash table.
+ * Actually frees the node->name
+ */
+static void destroy_string(void *key)
+{
+    g_free(key);
+}
+
+/**
+ * search_node(): search for a node @key in the nodes hash table
+ * Returns the QOSGraphNode if found, #NULL otherwise
+ */
+static QOSGraphNode *search_node(const char *key)
+{
+    return g_hash_table_lookup(node_table, key);
+}
+
+/**
+ * get_edgelist(): returns the edge list (value) assigned to
+ * the @key in the edge hash table.
+ * This list will contain all edges with source equal to @key
+ *
+ * Returns: on success: the %QOSGraphEdgeList
+ *          otherwise: abort()
+ */
+static QOSGraphEdgeList *get_edgelist(const char *key)
+{
+    return g_hash_table_lookup(edge_table, key);
+}
+
+/**
+ * search_list_edges(): search for an edge with destination @dest
+ * in the given @edgelist.
+ *
+ * Returns: on success: the %QOSGraphEdge
+ *          otherwise: #NULL
+ */
+static QOSGraphEdge *search_list_edges(QOSGraphEdgeList *edgelist,
+                                       const char *dest)
+{
+    QOSGraphEdge *tmp, *next;
+    if (!edgelist) {
+        return NULL;
+    }
+    QSLIST_FOREACH_SAFE(tmp, edgelist, edge_list, next) {
+        if (g_strcmp0(tmp->dest, dest) == 0) {
+            break;
+        }
+    }
+    return tmp;
+}
+
+/**
+ * search_machine(): search for a machine @name in the node hash
+ * table. A machine is the child of the root node.
+ * This function forces the research in the childs of the root,
+ * to check the node is a proper machine
+ *
+ * Returns: on success: the %QOSGraphNode
+ *          otherwise: #NULL
+ */
+static QOSGraphNode *search_machine(const char *name)
+{
+    QOSGraphNode *n;
+    QOSGraphEdgeList *root_list = get_edgelist(QOS_ROOT);
+    QOSGraphEdge *e = search_list_edges(root_list, name);
+    if (!e) {
+        return NULL;
+    }
+    n = search_node(e->dest);
+    if (n->type == QNODE_MACHINE) {
+        return n;
+    }
+    return NULL;
+}
+
+/**
+ * create_interface(): checks if there is already
+ * a node @node in the node hash table, if not
+ * creates a node @node of type #QNODE_INTERFACE
+ * and inserts it. If there is one, check it's
+ * a #QNODE_INTERFACE and abort() if it's not.
+ */
+static void create_interface(const char *node)
+{
+    QOSGraphNode *interface;
+    interface = search_node(node);
+    if (!interface) {
+        create_node(node, QNODE_INTERFACE);
+    } else if (interface->type != QNODE_INTERFACE) {
+        fprintf(stderr, "Error: Node %s is not an interface\n", node);
+        abort();
+    }
+}
+
+/**
+ * build_machine_cmd_line(): builds the command line for the machine
+ * @node. The node name must be a valid qemu identifier, since it
+ * will be used to build the command line.
+ *
+ * It is also possible to pass an optional @args that will be
+ * concatenated to the command line.
+ *
+ * For machines, prepend -M to the machine name. ", @rgs" is added
+ * after the -M <machine> command.
+ */
+static void build_machine_cmd_line(QOSGraphNode *node, const char *args)
+{
+    char *machine = qos_get_machine_type(node->name);
+    if (args) {
+        node->command_line = g_strconcat("-M ", machine, ",", args, NULL);
+    } else {
+        node->command_line = g_strconcat("-M ", machine, " ", NULL);
+    }
+}
+
+/**
+ * build_driver_cmd_line(): builds the command line for the driver
+ * @node. The node name must be a valid qemu identifier, since it
+ * will be used to build the command line.
+ *
+ * Driver do not need additional command line, since it will be
+ * provided by the edge options.
+ *
+ * For drivers, prepend -device to the node name.
+ */
+static void build_driver_cmd_line(QOSGraphNode *node)
+{
+    node->command_line = g_strconcat(" -device ", node->name, NULL);
+}
+
+/* qos_print_cb(): callback prints all path found by the DFS algorithm. */
+static void qos_print_cb(QOSGraphNode *path, int length)
+{
+    #if QGRAPH_PRINT_DEBUG
+        printf("%d elements\n", length);
+
+        if (!path) {
+            return;
+        }
+
+        while (path->path_edge) {
+            printf("%s ", path->name);
+            switch (path->path_edge->type) {
+            case QEDGE_PRODUCES:
+                printf("--PRODUCES--> ");
+                break;
+            case QEDGE_CONSUMED_BY:
+                printf("--CONSUMED_BY--> ");
+                break;
+            case QEDGE_CONTAINS:
+                printf("--CONTAINS--> ");
+                break;
+            }
+            path = search_node(path->path_edge->dest);
+        }
+
+        printf("%s\n\n", path->name);
+    #endif
+}
+
+/* qos_push(): push a node @el and edge @e in the qos_node_stack */
+static void qos_push(QOSGraphNode *el, QOSStackElement *parent,
+                     QOSGraphEdge *e)
+{
+    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) {
+        .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];
+}
+
+/* qos_pop(): pops an element from the tos, setting it unvisited*/
+static QOSStackElement *qos_pop(void)
+{
+    if (qos_node_tos == 0) {
+        g_printerr("QOSStack: empty stack, cannot pop");
+        abort();
+    }
+    QOSStackElement *e = qos_tos();
+    e->node->visited = false;
+    qos_node_tos--;
+    return e;
+}
+
+/**
+ * qos_reverse_path(): reverses the found path, going from
+ * test-to-machine to machine-to-test
+ */
+static QOSGraphNode *qos_reverse_path(QOSStackElement *el)
+{
+    if (!el) {
+        return NULL;
+    }
+
+    el->node->path_edge = NULL;
+
+    while (el->parent) {
+        el->parent->node->path_edge = el->parent_edge;
+        el = el->parent;
+    }
+
+    return el->node;
+}
+
+/**
+ * qos_traverse_graph(): graph-walking algorithm, using Depth First Search it
+ * starts from the root @machine and walks all possible path until it
+ * reaches a test node.
+ * At that point, it reverses the path found and invokes the @callback.
+ *
+ * Being Depth First Search, time complexity is O(|V| + |E|), while
+ * space is O(|V|). In this case, the maximum stack size is set by
+ * QOS_PATH_MAX_ELEMENT_SIZE.
+ */
+static void qos_traverse_graph(QOSGraphNode *root, QOSTestCallback callback)
+{
+    QOSGraphNode *v, *dest_node, *path;
+    QOSStackElement *s_el;
+    QOSGraphEdge *e, *next;
+    QOSGraphEdgeList *list;
+
+    qos_push(root, NULL, NULL);
+
+    while (qos_node_tos > 0) {
+        s_el = qos_tos();
+        v = s_el->node;
+        if (v->visited) {
+            qos_pop();
+            continue;
+        }
+        v->visited = true;
+        list = get_edgelist(v->name);
+        if (!list) {
+            qos_pop();
+            if (v->type == QNODE_TEST) {
+                v->visited = false;
+                path = qos_reverse_path(s_el);
+                callback(path, s_el->length);
+            }
+        } else {
+            QSLIST_FOREACH_SAFE(e, list, edge_list, next) {
+                dest_node = search_node(e->dest);
+
+                if (!dest_node) {
+                    fprintf(stderr, "node %s in %s -> %s does not exist\n",
+                            e->dest, v->name, e->dest);
+                    abort();
+                }
+
+                if (!dest_node->visited && dest_node->available) {
+                    qos_push(dest_node, s_el, e);
+                }
+            }
+        }
+    }
+}
+
+/* QGRAPH API*/
+
+QOSGraphNode *qos_graph_get_node(const char *key)
+{
+    return search_node(key);
+}
+
+bool qos_graph_has_node(const char *node)
+{
+    QOSGraphNode *n = search_node(node);
+    return n != NULL;
+}
+
+QOSNodeType qos_graph_get_node_type(const char *node)
+{
+    QOSGraphNode *n = search_node(node);
+    if (n) {
+        return n->type;
+    }
+    return -1;
+}
+
+bool qos_graph_get_node_availability(const char *node)
+{
+    QOSGraphNode *n = search_node(node);
+    if (n) {
+        return n->available;
+    }
+    return false;
+}
+
+QOSGraphEdge *qos_graph_get_edge(const char *node, const char *dest)
+{
+    QOSGraphEdgeList *list = get_edgelist(node);
+    return search_list_edges(list, dest);
+}
+
+QOSEdgeType qos_graph_edge_get_type(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return -1;
+    }
+    return edge->type;;
+}
+
+char *qos_graph_edge_get_dest(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->dest;
+}
+
+void *qos_graph_edge_get_arg(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->arg;
+}
+
+char *qos_graph_edge_get_after_cmd_line(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->after_cmd_line;
+}
+
+char *qos_graph_edge_get_before_cmd_line(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->before_cmd_line;
+}
+
+char *qos_graph_edge_get_extra_device_opts(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->extra_device_opts;
+}
+
+char *qos_graph_edge_get_name(QOSGraphEdge *edge)
+{
+    if (!edge) {
+        return NULL;
+    }
+    return edge->edge_name;
+}
+
+bool qos_graph_has_edge(const char *start, const char *dest)
+{
+    QOSGraphEdgeList *list = get_edgelist(start);
+    QOSGraphEdge *e = search_list_edges(list, dest);
+    return e != NULL;
+}
+
+QOSGraphNode *qos_graph_get_machine(const char *node)
+{
+    return search_machine(node);
+}
+
+bool qos_graph_has_machine(const char *node)
+{
+    QOSGraphNode *m = search_machine(node);
+    return m != NULL;
+}
+
+void qos_print_graph(void)
+{
+    qos_graph_foreach_test_path(qos_print_cb);
+}
+
+void qos_graph_init(void)
+{
+    if (!node_table) {
+        node_table = g_hash_table_new_full(g_str_hash, g_str_equal,
+                                           destroy_string, destroy_node);
+        create_node(QOS_ROOT, QNODE_DRIVER);
+    }
+
+    if (!edge_table) {
+        edge_table = g_hash_table_new_full(g_str_hash, g_str_equal,
+                                           destroy_string, destroy_edges);
+    }
+}
+
+void qos_graph_destroy(void)
+{
+    if (node_table) {
+        g_hash_table_destroy(node_table);
+    }
+
+    if (edge_table) {
+        g_hash_table_destroy(edge_table);
+    }
+
+    node_table = NULL;
+    edge_table = NULL;
+}
+
+void qos_node_destroy(void *key)
+{
+    g_hash_table_remove(node_table, key);
+}
+
+void qos_edge_destroy(void *key)
+{
+    g_hash_table_remove(edge_table, key);
+}
+
+void qos_add_test(const char *name, const char *interface,
+                  QOSTestFunc test_func, QOSGraphTestOptions *opts)
+{
+    QOSGraphNode *node;
+    char *test_name = g_strdup_printf("%s-tests/%s", interface, name);;
+
+    if (!opts) {
+        opts = &(QOSGraphTestOptions) { };
+    }
+    node = create_node(test_name, QNODE_TEST);
+    node->u.test.function = test_func;
+    node->u.test.arg = opts->arg;
+    assert(!opts->edge.arg);
+    assert(!opts->edge.size_arg);
+
+    node->u.test.before = opts->before;
+    node->u.test.subprocess = opts->subprocess;
+    node->available = true;
+    add_edge(interface, test_name, QEDGE_CONSUMED_BY, &opts->edge);
+    g_free(test_name);
+}
+
+void qos_node_create_machine(const char *name, QOSCreateMachineFunc function)
+{
+    qos_node_create_machine_args(name, function, NULL);
+}
+
+void qos_node_create_machine_args(const char *name,
+                                  QOSCreateMachineFunc function,
+                                  const char *opts)
+{
+    QOSGraphNode *node = create_node(name, QNODE_MACHINE);
+    build_machine_cmd_line(node, opts);
+    node->u.machine.constructor = function;
+    add_edge(QOS_ROOT, name, QEDGE_CONTAINS, NULL);
+}
+
+void qos_node_create_driver(const char *name, QOSCreateDriverFunc function)
+{
+    QOSGraphNode *node = create_node(name, QNODE_DRIVER);
+    build_driver_cmd_line(node);
+    node->u.driver.constructor = function;
+}
+
+void qos_node_contains(const char *container, const char *contained,
+                       ...)
+{
+    va_list va;
+    va_start(va, contained);
+    QOSGraphEdgeOptions *opts;
+
+    do {
+        opts = va_arg(va, QOSGraphEdgeOptions *);
+        add_edge(container, contained, QEDGE_CONTAINS, opts);
+    } while (opts != NULL);
+
+    va_end(va);
+}
+
+void qos_node_produces(const char *producer, const char *interface)
+{
+    create_interface(interface);
+    add_edge(producer, interface, QEDGE_PRODUCES, NULL);
+}
+
+void qos_node_consumes(const char *consumer, const char *interface,
+                       QOSGraphEdgeOptions *opts)
+{
+    create_interface(interface);
+    add_edge(interface, consumer, QEDGE_CONSUMED_BY, opts);
+}
+
+void qos_graph_node_set_availability(const char *node, bool av)
+{
+    QOSGraphEdgeList *elist;
+    QOSGraphNode *n = search_node(node);
+    QOSGraphEdge *e, *next;
+    if (!n) {
+        return;
+    }
+    n->available = av;
+    elist = get_edgelist(node);
+    if (!elist) {
+        return;
+    }
+    QSLIST_FOREACH_SAFE(e, elist, edge_list, next) {
+        if (e->type == QEDGE_CONTAINS || e->type == QEDGE_PRODUCES) {
+            qos_graph_node_set_availability(e->dest, av);
+        }
+    }
+}
+
+void qos_graph_foreach_test_path(QOSTestCallback fn)
+{
+    QOSGraphNode *root = qos_graph_get_node(QOS_ROOT);
+    qos_traverse_graph(root, fn);
+}
+
+QOSGraphObject *qos_machine_new(QOSGraphNode *node, QTestState *qts)
+{
+    QOSGraphObject *obj;
+
+    g_assert(node->type == QNODE_MACHINE);
+    obj = node->u.machine.constructor(qts);
+    obj->free = g_free;
+    return obj;
+}
+
+QOSGraphObject *qos_driver_new(QOSGraphNode *node, QOSGraphObject *parent,
+                               QGuestAllocator *alloc, void *arg)
+{
+    QOSGraphObject *obj;
+
+    g_assert(node->type == QNODE_DRIVER);
+    obj = node->u.driver.constructor(parent, alloc, arg);
+    obj->free = g_free;
+    return obj;
+}
+
+void qos_object_destroy(QOSGraphObject *obj)
+{
+    if (!obj) {
+        return;
+    }
+    if (obj->destructor) {
+        obj->destructor(obj);
+    }
+    if (obj->free) {
+        obj->free(obj);
+    }
+}
+
+void qos_object_queue_destroy(QOSGraphObject *obj)
+{
+    g_test_queue_destroy((GDestroyNotify) qos_object_destroy, obj);
+}
+
+void qos_object_start_hw(QOSGraphObject *obj)
+{
+    if (obj->start_hw) {
+        obj->start_hw(obj);
+    }
+}
+
+char *qos_get_machine_type(char *name)
+{
+    while (*name != '\0' && *name != '/') {
+        name++;
+    }
+
+    if (!*name || !name[1]) {
+        fprintf(stderr, "Machine name has to be of the form <arch>/<machine>\n");
+        abort();
+    }
+
+    return name + 1;
+}
+
+void qos_delete_cmd_line(const char *name)
+{
+    QOSGraphNode *node = search_node(name);
+    if (node) {
+        g_free(node->command_line);
+        node->command_line = NULL;
+    }
+}
diff --git a/tests/libqos/qgraph.h b/tests/libqos/qgraph.h
new file mode 100644
index 0000000000..ef0c73837a
--- /dev/null
+++ b/tests/libqos/qgraph.h
@@ -0,0 +1,575 @@
+/*
+ * libqos driver framework
+ *
+ * Copyright (c) 2018 Emanuele Giuseppe Esposito <e.emanuelegiuseppe@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2 as published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>
+ */
+
+#ifndef QGRAPH_H
+#define QGRAPH_H
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <gmodule.h>
+#include <glib.h>
+#include "qemu/module.h"
+#include "malloc.h"
+
+/* maximum path length */
+#define QOS_PATH_MAX_ELEMENT_SIZE 50
+
+typedef struct QOSGraphObject QOSGraphObject;
+typedef struct QOSGraphNode QOSGraphNode;
+typedef struct QOSGraphEdge QOSGraphEdge;
+typedef struct QOSGraphNodeOptions QOSGraphNodeOptions;
+typedef struct QOSGraphEdgeOptions QOSGraphEdgeOptions;
+typedef struct QOSGraphTestOptions QOSGraphTestOptions;
+
+/* Constructor for drivers, machines and test */
+typedef void *(*QOSCreateDriverFunc) (void *parent, QGuestAllocator *alloc,
+                                      void *addr);
+typedef void *(*QOSCreateMachineFunc) (QTestState *qts);
+typedef void (*QOSTestFunc) (void *parent, void *arg, QGuestAllocator *alloc);
+
+/* QOSGraphObject functions */
+typedef void *(*QOSGetDriver) (void *object, const char *interface);
+typedef QOSGraphObject *(*QOSGetDevice) (void *object, const char *name);
+typedef void (*QOSDestructorFunc) (QOSGraphObject *object);
+typedef void (*QOSStartFunct) (QOSGraphObject *object);
+
+/* Test options functions */
+typedef void *(*QOSBeforeTest) (GString *cmd_line, void *arg);
+
+/**
+ * SECTION: qgraph.h
+ * @title: Qtest Driver Framework
+ * @short_description: interfaces to organize drivers and tests
+ *                     as nodes in a graph
+ *
+ * This Qgraph API provides all basic functions to create a graph
+ * and instantiate nodes representing machines, drivers and tests
+ * representing their relations with CONSUMES, PRODUCES, and CONTAINS
+ * edges.
+ *
+ * The idea is to have a framework where each test asks for a specific
+ * driver, and the framework takes care of allocating the proper devices
+ * required and passing the correct command line arguments to QEMU.
+ *
+ * A node can be of four types:
+ * - QNODE_MACHINE:   for example "arm/raspi2"
+ * - QNODE_DRIVER:    for example "generic-sdhci"
+ * - QNODE_INTERFACE: for example "sdhci" (interface for all "-sdhci" drivers)
+ *                     an interface is not explicitly created, it will be auto-
+ *                     matically instantiated when a node consumes or produces
+ *                     it.
+ * - QNODE_TEST:      for example "sdhci-test", consumes an interface and tests
+ *                    the functions provided
+ *
+ * Notes for the nodes:
+ * - QNODE_MACHINE: each machine struct must have a QGuestAllocator and
+ *                  implement get_driver to return the allocator passing
+ *                  "memory". The function can also return NULL if the
+ *                  allocator is not set.
+ * - QNODE_DRIVER:  driver names must be unique, and machines and nodes
+ *                  planned to be "consumed" by other nodes must match QEMU
+ *                  drivers name, otherwise they won't be discovered
+ *
+ * An edge relation between two nodes (drivers or machines) X and Y can be:
+ * - X CONSUMES Y: Y can be plugged into X
+ * - X PRODUCES Y: X provides the interface Y
+ * - X CONTAINS Y: Y is part of X component
+ *
+ * Basic framework steps are the following:
+ * - All nodes and edges are created in their respective
+ *   machine/driver/test files
+ * - The framework starts QEMU and asks for a list of available devices
+ *   and machines (note that only machines and "consumed" nodes are mapped
+ *   1:1 with QEMU devices)
+ * - The framework walks the graph starting from the available machines and
+ *   performs a Depth First Search for tests
+ * - Once a test is found, the path is walked again and all drivers are
+ *   allocated accordingly and the final interface is passed to the test
+ * - The test is executed
+ * - Unused objects are cleaned and the path discovery is continued
+ *
+ * Depending on the QEMU binary used, only some drivers/machines will be
+ * available and only test that are reached by them will be executed.
+ *
+ * <example>
+ *   <title>Creating new driver an its interface</title>
+ *   <programlisting>
+ #include "libqos/qgraph.h"
+
+ struct My_driver {
+     QOSGraphObject obj;
+     Node_produced prod;
+     Node_contained cont;
+ }
+
+ static void my_destructor(QOSGraphObject *obj)
+ {
+    g_free(obj);
+ }
+
+ static void my_get_driver(void *object, const char *interface) {
+    My_driver *dev = object;
+    if (!g_strcmp0(interface, "my_interface")) {
+        return &dev->prod;
+    }
+    abort();
+ }
+
+ static void my_get_device(void *object, const char *device) {
+    My_driver *dev = object;
+    if (!g_strcmp0(device, "my_driver_contained")) {
+        return &dev->cont;
+    }
+    abort();
+ }
+
+ static void *my_driver_constructor(void *node_consumed,
+                                    QOSGraphObject *alloc)
+ {
+    My_driver dev = g_new(My_driver, 1);
+    // get the node pointed by the produce edge
+    dev->obj.get_driver = my_get_driver;
+    // get the node pointed by the contains
+    dev->obj.get_device = my_get_device;
+    // free the object
+    dev->obj.destructor = my_destructor;
+    do_something_with_node_consumed(node_consumed);
+    // set all fields of contained device
+    init_contained_device(&dev->cont);
+    return &dev->obj;
+ }
+
+ static void register_my_driver(void)
+ {
+     qos_node_create_driver("my_driver", my_driver_constructor);
+     // contained drivers don't need a constructor,
+     // they will be init by the parent.
+     qos_node_create_driver("my_driver_contained", NULL);
+
+    // For the sake of this example, assume machine x86_64/pc contains
+    // "other_node".
+    // This relation, along with the machine and "other_node" creation,
+    // should be defined in the x86_64_pc-machine.c file.
+    // "my_driver" will then consume "other_node"
+    qos_node_contains("my_driver", "my_driver_contained");
+    qos_node_produces("my_driver", "my_interface");
+    qos_node_consumes("my_driver", "other_node");
+ }
+ *   </programlisting>
+ * </example>
+ *
+ * In the above example, all possible types of relations are created:
+ * node "my_driver" consumes, contains and produces other nodes.
+ * more specifically:
+ * x86_64/pc -->contains--> other_node <--consumes-- my_driver
+ *                                                       |
+ *                      my_driver_contained <--contains--+
+ *                                                       |
+ *                             my_interface <--produces--+
+ *
+ * or inverting the consumes edge in consumed_by:
+ *
+ * x86_64/pc -->contains--> other_node --consumed_by--> my_driver
+ *                                                           |
+ *                          my_driver_contained <--contains--+
+ *                                                           |
+ *                                 my_interface <--produces--+
+ *
+ * <example>
+ *   <title>Creating new test</title>
+ *   <programlisting>
+ * #include "libqos/qgraph.h"
+ *
+ * static void my_test_function(void *obj, void *data)
+ * {
+ *    Node_produced *interface_to_test = obj;
+ *    // test interface_to_test
+ * }
+ *
+ * static void register_my_test(void)
+ * {
+ *    qos_add_test("my_interface", "my_test", my_test_function);
+ * }
+ *
+ * libqos_init(register_my_test);
+ *
+ *   </programlisting>
+ * </example>
+ *
+ * Here a new test is created, consuming "my_interface" node
+ * and creating a valid path from a machine to a test.
+ * Final graph will be like this:
+ * x86_64/pc -->contains--> other_node <--consumes-- my_driver
+ *                                                        |
+ *                       my_driver_contained <--contains--+
+ *                                                        |
+ *        my_test --consumes--> my_interface <--produces--+
+ *
+ * or inverting the consumes edge in consumed_by:
+ *
+ * x86_64/pc -->contains--> other_node --consumed_by--> my_driver
+ *                                                           |
+ *                          my_driver_contained <--contains--+
+ *                                                           |
+ *        my_test <--consumed_by-- my_interface <--produces--+
+ *
+ * Assuming there the binary is
+ * QTEST_QEMU_BINARY=x86_64-softmmu/qemu-system-x86_64
+ * a valid test path will be:
+ * "/x86_64/pc/other_node/my_driver/my_interface/my_test".
+ *
+ * Additional examples are also in libqos/test-qgraph.c
+ *
+ * Command line:
+ * Command line is built by using node names and optional arguments
+ * passed by the user when building the edges.
+ *
+ * There are three types of command line arguments:
+ * - in node      : created from the node name. For example, machines will
+ *                  have "-M <machine>" to its command line, while devices
+ *                  "-device <device>". It is automatically done by the
+ *                   framework.
+ * - after node   : added as additional argument to the node name.
+ *                  This argument is added optionally when creating edges,
+ *                  by setting the parameter @after_cmd_line and
+ *                  @extra_edge_opts in #QOSGraphEdgeOptions.
+ *                  The framework automatically adds
+ *                  a comma before @extra_edge_opts,
+ *                  because it is going to add attributes
+ *                  after the destination node pointed by
+ *                  the edge containing these options, and automatically
+ *                  adds a space before @after_cmd_line, because it
+ *                  adds an additional device, not an attribute.
+ * - before node  : added as additional argument to the node name.
+ *                  This argument is added optionally when creating edges,
+ *                  by setting the parameter @before_cmd_line in
+ *                  #QOSGraphEdgeOptions. This attribute
+ *                  is going to add attributes before the destination node
+ *                  pointed by the edge containing these options. It is
+ *                  helpful to commands that are not node-representable,
+ *                  such as "-fdsev" or "-netdev".
+ *
+ * While adding command line in edges is always used, not all nodes names are
+ * used in every path walk: this is because the contained or produced ones
+ * are already added by QEMU, so only nodes that "consumes" will be used to
+ * build the command line. Also, nodes that will have { "abstract" : true }
+ * as QMP attribute will loose their command line, since they are not proper
+ * devices to be added in QEMU.
+ *
+ * Example:
+ *
+ QOSGraphEdgeOptions opts = {
+     .arg = NULL,
+     .size_arg = 0,
+     .after_cmd_line = "-device other",
+     .before_cmd_line = "-netdev something",
+     .extra_edge_opts = "addr=04.0",
+ };
+ QOSGraphNode * node = qos_node_create_driver("my_node", constructor);
+ qos_node_consumes_args("my_node", "interface", &opts);
+ *
+ * Will produce the following command line:
+ * "-netdev something -device my_node,addr=04.0 -device other"
+ */
+
+/**
+ * Edge options to be passed to the contains/consumes *_args function.
+ */
+struct QOSGraphEdgeOptions {
+    void *arg;                    /*
+                                   * optional arg that will be used by
+                                   * dest edge
+                                   */
+    uint32_t size_arg;            /*
+                                   * optional arg size that will be used by
+                                   * dest edge
+                                   */
+    const char *extra_device_opts;/*
+                                   *optional additional command line for dest
+                                   * edge, used to add additional attributes
+                                   * *after* the node command line, the
+                                   * framework automatically prepends ","
+                                   * to this argument.
+                                   */
+    const char *before_cmd_line;  /*
+                                   * optional additional command line for dest
+                                   * edge, used to add additional attributes
+                                   * *before* the node command line, usually
+                                   * other non-node represented commands,
+                                   * like "-fdsev synt"
+                                   */
+    const char *after_cmd_line;   /*
+                                   * optional extra command line to be added
+                                   * after the device command. This option
+                                   * is used to add other devices
+                                   * command line that depend on current node.
+                                   * Automatically prepends " " to this
+                                   * argument
+                                   */
+    const char *edge_name;        /*
+                                   * optional edge to differentiate multiple
+                                   * devices with same node name
+                                   */
+};
+
+/**
+ * Test options to be passed to the test functions.
+ */
+struct QOSGraphTestOptions {
+    QOSGraphEdgeOptions edge;   /* edge arguments that will be used by test.
+                                 * Note that test *does not* use edge_name,
+                                 * and uses instead arg and size_arg as
+                                 * data arg for its test function.
+                                 */
+    void *arg;                  /* passed to the .before function, or to the
+                                 * test function if there is no .before
+                                 * function
+                                 */
+    QOSBeforeTest before;       /* executed before the test. Can add
+                                 * additional parameters to the command line
+                                 * and modify the argument to the test function.
+                                 */
+    bool subprocess;            /* run the test in a subprocess */
+};
+
+/**
+ * Each driver, test or machine of this framework will have a
+ * QOSGraphObject as first field.
+ *
+ * This set of functions offered by QOSGraphObject are executed
+ * in different stages of the framework:
+ * - get_driver / get_device : Once a machine-to-test path has been
+ * found, the framework traverses it again and allocates all the
+ * nodes, using the provided constructor. To satisfy their relations,
+ * i.e. for produces or contains, where a struct constructor needs
+ * an external parameter represented by the previous node,
+ * the framework will call get_device (for contains) or
+ * get_driver (for produces), depending on the edge type, passing
+ * them the name of the next node to be taken and getting from them
+ * the corresponding pointer to the actual structure of the next node to
+ * be used in the path.
+ *
+ * - start_hw: This function is executed after all the path objects
+ * have been allocated, but before the test is run. It starts the hw, setting
+ * the initial configurations (*_device_enable) and making it ready for the
+ * test.
+ *
+ * - destructor: Opposite to the node constructor, destroys the object.
+ * This function is called after the test has been executed, and performs
+ * a complete cleanup of each node allocated field. In case no constructor
+ * is provided, no destructor will be called.
+ *
+ */
+struct QOSGraphObject {
+    /* for produces edges, returns void * */
+    QOSGetDriver get_driver;
+    /* for contains edges, returns a QOSGraphObject * */
+    QOSGetDevice get_device;
+    /* start the hw, get ready for the test */
+    QOSStartFunct start_hw;
+    /* destroy this QOSGraphObject */
+    QOSDestructorFunc destructor;
+    /* free the memory associated to the QOSGraphObject and its contained
+     * children */
+    GDestroyNotify free;
+};
+
+/**
+ * qos_graph_init(): initialize the framework, creates two hash
+ * tables: one for the nodes and another for the edges.
+ */
+void qos_graph_init(void);
+
+/**
+ * qos_graph_destroy(): deallocates all the hash tables,
+ * freeing all nodes and edges.
+ */
+void qos_graph_destroy(void);
+
+/**
+ * qos_node_destroy(): removes and frees a node from the,
+ * nodes hash table.
+ */
+void qos_node_destroy(void *key);
+
+/**
+ * qos_edge_destroy(): removes and frees an edge from the,
+ * edges hash table.
+ */
+void qos_edge_destroy(void *key);
+
+/**
+ * qos_add_test(): adds a test node @name to the nodes hash table.
+ *
+ * The test will consume a @interface node, and once the
+ * graph walking algorithm has found it, the @test_func will be
+ * executed. It also has the possibility to
+ * add an optional @opts (see %QOSGraphNodeOptions).
+ *
+ * For tests, opts->edge.arg and size_arg represent the arg to pass
+ * to @test_func
+ */
+void qos_add_test(const char *name, const char *interface,
+                  QOSTestFunc test_func,
+                  QOSGraphTestOptions *opts);
+
+/**
+ * qos_node_create_machine(): creates the machine @name and
+ * adds it to the node hash table.
+ *
+ * This node will be of type QNODE_MACHINE and have @function
+ * as constructor
+ */
+void qos_node_create_machine(const char *name, QOSCreateMachineFunc function);
+
+/**
+ * qos_node_create_machine_args(): same as qos_node_create_machine,
+ * but with the possibility to add an optional ", @opts" after -M machine
+ * command line.
+ */
+void qos_node_create_machine_args(const char *name,
+                                  QOSCreateMachineFunc function,
+                                  const char *opts);
+
+/**
+ * qos_node_create_driver(): creates the driver @name and
+ * adds it to the node hash table.
+ *
+ * This node will be of type QNODE_DRIVER and have @function
+ * as constructor
+ */
+void qos_node_create_driver(const char *name, QOSCreateDriverFunc function);
+
+/**
+ * qos_node_contains(): creates an edge of type QEDGE_CONTAINS and
+ * adds it to the edge list mapped to @container in the
+ * edge hash table.
+ *
+ * This edge will have @container as source and @contained as destination.
+ *
+ * It also has the possibility to add optional NULL-terminated
+ * @opts parameters (see %QOSGraphEdgeOptions)
+ *
+ * This function can be useful when there are multiple devices
+ * with the same node name contained in a machine/other node
+ *
+ * For example, if "arm/raspi2" contains 2 "generic-sdhci"
+ * devices, the right commands will be:
+ * qos_node_create_machine("arm/raspi2");
+ * qos_node_create_driver("generic-sdhci", constructor);
+ * //assume rest of the fields are set NULL
+ * QOSGraphEdgeOptions op1 = { .edge_name = "emmc" };
+ * QOSGraphEdgeOptions op2 = { .edge_name = "sdcard" };
+ * qos_node_contains("arm/raspi2", "generic-sdhci", &op1, &op2, NULL);
+ *
+ * Of course this also requires that the @container's get_device function
+ * should implement a case for "emmc" and "sdcard".
+ *
+ * For contains, op1.arg and op1.size_arg represent the arg to pass
+ * to @contained constructor to properly initialize it.
+ */
+void qos_node_contains(const char *container, const char *contained, ...);
+
+/**
+ * qos_node_produces(): creates an edge of type QEDGE_PRODUCES and
+ * adds it to the edge list mapped to @producer in the
+ * edge hash table.
+ *
+ * This edge will have @producer as source and @interface as destination.
+ */
+void qos_node_produces(const char *producer, const char *interface);
+
+/**
+ * qos_node_consumes():  creates an edge of type QEDGE_CONSUMED_BY and
+ * adds it to the edge list mapped to @interface in the
+ * edge hash table.
+ *
+ * This edge will have @interface as source and @consumer as destination.
+ * It also has the possibility to add an optional @opts
+ * (see %QOSGraphEdgeOptions)
+ */
+void qos_node_consumes(const char *consumer, const char *interface,
+                       QOSGraphEdgeOptions *opts);
+
+/**
+ * qos_invalidate_command_line(): invalidates current command line, so that
+ * qgraph framework cannot try to cache the current command line and
+ * forces QEMU to restart.
+ */
+void qos_invalidate_command_line(void);
+
+/**
+ * qos_get_current_command_line(): return the command line required by the
+ * machine and driver objects.  This is the same string that was passed to
+ * the test's "before" callback, if any.
+ */
+const char *qos_get_current_command_line(void);
+
+/**
+ * qos_allocate_objects():
+ * @qts: The #QTestState that will be referred to by the machine object.
+ * @alloc: Where to store the allocator for the machine object, or %NULL.
+ *
+ * Allocate driver objects for the current test
+ * path, but relative to the QTestState @qts.
+ *
+ * Returns a test object just like the one that was passed to
+ * the test function, but relative to @qts.
+ */
+void *qos_allocate_objects(QTestState *qts, QGuestAllocator **p_alloc);
+
+/**
+ * qos_object_destroy(): calls the destructor for @obj
+ */
+void qos_object_destroy(QOSGraphObject *obj);
+
+/**
+ * qos_object_queue_destroy(): queue the destructor for @obj so that it is
+ * called at the end of the test
+ */
+void qos_object_queue_destroy(QOSGraphObject *obj);
+
+/**
+ * qos_object_start_hw(): calls the start_hw function for @obj
+ */
+void qos_object_start_hw(QOSGraphObject *obj);
+
+/**
+ * qos_machine_new(): instantiate a new machine node
+ * @node: A machine node to be instantiated
+ * @qts: The #QTestState that will be referred to by the machine object.
+ *
+ * Returns a machine object.
+ */
+QOSGraphObject *qos_machine_new(QOSGraphNode *node, QTestState *qts);
+
+/**
+ * qos_machine_new(): instantiate a new driver node
+ * @node: A driver node to be instantiated
+ * @parent: A #QOSGraphObject to be consumed by the new driver node
+ * @alloc: An allocator to be used by the new driver node.
+ * @arg: The argument for the consumed-by edge to @node.
+ *
+ * Calls the constructor for the driver object.
+ */
+QOSGraphObject *qos_driver_new(QOSGraphNode *node, QOSGraphObject *parent,
+                               QGuestAllocator *alloc, void *arg);
+
+
+#endif
diff --git a/tests/libqos/qgraph_internal.h b/tests/libqos/qgraph_internal.h
new file mode 100644
index 0000000000..2ef748baf6
--- /dev/null
+++ b/tests/libqos/qgraph_internal.h
@@ -0,0 +1,257 @@
+/*
+ * libqos driver framework
+ *
+ * Copyright (c) 2018 Emanuele Giuseppe Esposito <e.emanuelegiuseppe@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2 as published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>
+ */
+
+#ifndef QGRAPH_EXTRA_H
+#define QGRAPH_EXTRA_H
+
+/* This header is declaring additional helper functions defined in
+ * libqos/qgraph.c
+ * It should not be included in tests
+ */
+
+#include "libqos/qgraph.h"
+
+typedef struct QOSGraphMachine QOSGraphMachine;
+typedef enum QOSEdgeType QOSEdgeType;
+typedef enum QOSNodeType QOSNodeType;
+
+/* callback called when the walk path algorithm found a
+ * valid path
+ */
+typedef void (*QOSTestCallback) (QOSGraphNode *path, int len);
+
+/* edge types*/
+enum QOSEdgeType {
+    QEDGE_CONTAINS,
+    QEDGE_PRODUCES,
+    QEDGE_CONSUMED_BY
+};
+
+/* node types*/
+enum QOSNodeType {
+    QNODE_MACHINE,
+    QNODE_DRIVER,
+    QNODE_INTERFACE,
+    QNODE_TEST
+};
+
+/* Graph Node */
+struct QOSGraphNode {
+    QOSNodeType type;
+    bool available;     /* set by QEMU via QMP, used during graph walk */
+    bool visited;       /* used during graph walk */
+    char *name;         /* used to identify the node */
+    char *command_line; /* used to start QEMU at test execution */
+    union {
+        struct {
+            QOSCreateDriverFunc constructor;
+        } driver;
+        struct {
+            QOSCreateMachineFunc constructor;
+        } machine;
+        struct {
+            QOSTestFunc function;
+            void *arg;
+            QOSBeforeTest before;
+            bool subprocess;
+        } test;
+    } u;
+
+    /**
+     * only used when traversing the path, never rely on that except in the
+     * qos_traverse_graph callback function
+     */
+    QOSGraphEdge *path_edge;
+};
+
+/**
+ * qos_graph_get_node(): returns the node mapped to that @key.
+ * It performs an hash map search O(1)
+ *
+ * Returns: on success: the %QOSGraphNode
+ *          otherwise: #NULL
+ */
+QOSGraphNode *qos_graph_get_node(const char *key);
+
+/**
+ * qos_graph_has_node(): returns #TRUE if the node
+ * has map has a node mapped to that @key.
+ */
+bool qos_graph_has_node(const char *node);
+
+/**
+ * qos_graph_get_node_type(): returns the %QOSNodeType
+ * of the node @node.
+ * It performs an hash map search O(1)
+ * Returns: on success: the %QOSNodeType
+ *          otherwise: #-1
+ */
+QOSNodeType qos_graph_get_node_type(const char *node);
+
+/**
+ * qos_graph_get_node_availability(): returns the availability (boolean)
+ * of the node @node.
+ */
+bool qos_graph_get_node_availability(const char *node);
+
+/**
+ * qos_graph_get_edge(): returns the edge
+ * linking of the node @node with @dest.
+ *
+ * Returns: on success: the %QOSGraphEdge
+ *          otherwise: #NULL
+ */
+QOSGraphEdge *qos_graph_get_edge(const char *node, const char *dest);
+
+/**
+ * qos_graph_edge_get_type(): returns the edge type
+ * of the edge @edge.
+ *
+ * Returns: on success: the %QOSEdgeType
+ *          otherwise: #-1
+ */
+QOSEdgeType qos_graph_edge_get_type(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_edge_get_dest(): returns the name of the node
+ * pointed as destination of edge @edge.
+ *
+ * Returns: on success: the destination
+ *          otherwise: #NULL
+ */
+char *qos_graph_edge_get_dest(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_has_edge(): returns #TRUE if there
+ * exists an edge from @start to @dest.
+ */
+bool qos_graph_has_edge(const char *start, const char *dest);
+
+/**
+ * qos_graph_edge_get_arg(): returns the args assigned
+ * to that @edge.
+ *
+ * Returns: on success: the arg
+ *          otherwise: #NULL
+ */
+void *qos_graph_edge_get_arg(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_edge_get_after_cmd_line(): returns the edge
+ * command line that will be added after all the node arguments
+ * and all the before_cmd_line arguments.
+ *
+ * Returns: on success: the char* arg
+ *          otherwise: #NULL
+ */
+char *qos_graph_edge_get_after_cmd_line(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_edge_get_before_cmd_line(): returns the edge
+ * command line that will be added before the node command
+ * line argument.
+ *
+ * Returns: on success: the char* arg
+ *          otherwise: #NULL
+ */
+char *qos_graph_edge_get_before_cmd_line(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_edge_get_extra_device_opts(): returns the arg
+ * command line that will be added to the node command
+ * line argument.
+ *
+ * Returns: on success: the char* arg
+ *          otherwise: #NULL
+ */
+char *qos_graph_edge_get_extra_device_opts(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_edge_get_name(): returns the name
+ * assigned to the destination node (different only)
+ * if there are multiple devices with the same node name
+ * e.g. a node has two "generic-sdhci", "emmc" and "sdcard"
+ * there will be two edges with edge_name ="emmc" and "sdcard"
+ *
+ * Returns always the char* edge_name
+ */
+char *qos_graph_edge_get_name(QOSGraphEdge *edge);
+
+/**
+ * qos_graph_get_machine(): returns the machine assigned
+ * to that @node name.
+ *
+ * It performs a search only trough the list of machines
+ * (i.e. the QOS_ROOT child).
+ *
+ * Returns: on success: the %QOSGraphNode
+ *          otherwise: #NULL
+ */
+QOSGraphNode *qos_graph_get_machine(const char *node);
+
+/**
+ * qos_graph_has_machine(): returns #TRUE if the node
+ * has map has a node mapped to that @node.
+ */
+bool qos_graph_has_machine(const char *node);
+
+
+/**
+ * qos_print_graph(): walks the graph and prints
+ * all machine-to-test paths.
+ */
+void qos_print_graph(void);
+
+/**
+ * qos_graph_foreach_test_path(): executes the Depth First search
+ * algorithm and applies @fn to all discovered paths.
+ *
+ * See qos_traverse_graph() in qgraph.c for more info on
+ * how it works.
+ */
+void qos_graph_foreach_test_path(QOSTestCallback fn);
+
+/**
+ * qos_get_machine_type(): return QEMU machine type for a machine node.
+ * This function requires every machine @name to be in the form
+ * <arch>/<machine_name>, like "arm/raspi2" or "x86_64/pc".
+ *
+ * The function will validate the format and return a pointer to
+ * @machine to <machine_name>.  For example, when passed "x86_64/pc"
+ * it will return "pc".
+ *
+ * Note that this function *does not* allocate any new string.
+ */
+char *qos_get_machine_type(char *name);
+
+/**
+ * qos_delete_cmd_line(): delete the
+ * command line present in node mapped with key @name.
+ *
+ * This function is called when the QMP query returns a node with
+ * { "abstract" : true } attribute.
+ */
+void qos_delete_cmd_line(const char *name);
+
+/**
+ * qos_graph_node_set_availability(): sets the node identified
+ * by @node with availability @av.
+ */
+void qos_graph_node_set_availability(const char *node, bool av);
+
+#endif