qemu/tests/qtest/libqos/qgraph.c
<<
>>
Prefs
   1/*
   2 * libqos driver framework
   3 *
   4 * Copyright (c) 2018 Emanuele Giuseppe Esposito <e.emanuelegiuseppe@gmail.com>
   5 *
   6 * This library is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU Lesser General Public
   8 * License version 2.1 as published by the Free Software Foundation.
   9 *
  10 * This library is distributed in the hope that it will be useful,
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 * Lesser General Public License for more details.
  14 *
  15 * You should have received a copy of the GNU Lesser General Public
  16 * License along with this library; if not, see <http://www.gnu.org/licenses/>
  17 */
  18
  19#include "qemu/osdep.h"
  20#include "../libqtest.h"
  21#include "qemu/queue.h"
  22#include "qgraph_internal.h"
  23#include "qgraph.h"
  24
  25#define QGRAPH_PRINT_DEBUG 0
  26#define QOS_ROOT ""
  27typedef struct QOSStackElement QOSStackElement;
  28
  29/* Graph Edge.*/
  30struct QOSGraphEdge {
  31    QOSEdgeType type;
  32    char *dest;
  33    void *arg;                /* just for QEDGE_CONTAINS
  34                               * and QEDGE_CONSUMED_BY */
  35    char *extra_device_opts;  /* added to -device option, "," is
  36                               * automatically added
  37                               */
  38    char *before_cmd_line;    /* added before node cmd_line */
  39    char *after_cmd_line;     /* added after -device options */
  40    char *edge_name;          /* used by QEDGE_CONTAINS */
  41    QSLIST_ENTRY(QOSGraphEdge) edge_list;
  42};
  43
  44typedef QSLIST_HEAD(, QOSGraphEdge) QOSGraphEdgeList;
  45
  46/**
  47 * Stack used to keep track of the discovered path when using
  48 * the DFS algorithm
  49 */
  50struct QOSStackElement {
  51    QOSGraphNode *node;
  52    QOSStackElement *parent;
  53    QOSGraphEdge *parent_edge;
  54    int length;
  55};
  56
  57/* Each enty in these hash table will consist of <string, node/edge> pair. */
  58static GHashTable *edge_table;
  59static GHashTable *node_table;
  60
  61/* stack used by the DFS algorithm to store the path from machine to test */
  62static QOSStackElement qos_node_stack[QOS_PATH_MAX_ELEMENT_SIZE];
  63static int qos_node_tos;
  64
  65/**
  66 * add_edge(): creates an edge of type @type
  67 * from @source to @dest node, and inserts it in the
  68 * edges hash table
  69 *
  70 * Nodes @source and @dest do not necessarily need to exist.
  71 * Possibility to add also options (see #QOSGraphEdgeOptions)
  72 * edge->edge_name is used as identifier for get_device relationships,
  73 * so by default is equal to @dest.
  74 */
  75static void add_edge(const char *source, const char *dest,
  76                     QOSEdgeType type, QOSGraphEdgeOptions *opts)
  77{
  78    char *key;
  79    QOSGraphEdgeList *list = g_hash_table_lookup(edge_table, source);
  80    QOSGraphEdgeOptions def_opts = { };
  81
  82    if (!list) {
  83        list = g_new0(QOSGraphEdgeList, 1);
  84        key = g_strdup(source);
  85        g_hash_table_insert(edge_table, key, list);
  86    }
  87
  88    if (!opts) {
  89        opts = &def_opts;
  90    }
  91
  92    QOSGraphEdge *edge = g_new0(QOSGraphEdge, 1);
  93    edge->type = type;
  94    edge->dest = g_strdup(dest);
  95    edge->edge_name = g_strdup(opts->edge_name ?: dest);
  96    edge->arg = g_memdup2(opts->arg, opts->size_arg);
  97
  98    edge->before_cmd_line =
  99        opts->before_cmd_line ? g_strconcat(" ", opts->before_cmd_line, NULL) : NULL;
 100    edge->extra_device_opts =
 101        opts->extra_device_opts ? g_strconcat(",", opts->extra_device_opts, NULL) : NULL;
 102    edge->after_cmd_line =
 103        opts->after_cmd_line ? g_strconcat(" ", opts->after_cmd_line, NULL) : NULL;
 104
 105    QSLIST_INSERT_HEAD(list, edge, edge_list);
 106}
 107
 108/* destroy_edges(): frees all edges inside a given @list */
 109static void destroy_edges(void *list)
 110{
 111    QOSGraphEdge *temp;
 112    QOSGraphEdgeList *elist = list;
 113
 114    while (!QSLIST_EMPTY(elist)) {
 115        temp = QSLIST_FIRST(elist);
 116        QSLIST_REMOVE_HEAD(elist, edge_list);
 117        g_free(temp->dest);
 118        g_free(temp->before_cmd_line);
 119        g_free(temp->after_cmd_line);
 120        g_free(temp->extra_device_opts);
 121        g_free(temp->edge_name);
 122        g_free(temp->arg);
 123        g_free(temp);
 124    }
 125    g_free(elist);
 126}
 127
 128/**
 129 * create_node(): creates a node @name of type @type
 130 * and inserts it to the nodes hash table.
 131 * By default, node is not available.
 132 */
 133static QOSGraphNode *create_node(const char *name, QOSNodeType type)
 134{
 135    if (g_hash_table_lookup(node_table, name)) {
 136        g_printerr("Node %s already created\n", name);
 137        abort();
 138    }
 139
 140    QOSGraphNode *node = g_new0(QOSGraphNode, 1);
 141    node->type = type;
 142    node->available = false;
 143    node->name = g_strdup(name);
 144    g_hash_table_insert(node_table, node->name, node);
 145    return node;
 146}
 147
 148/**
 149 * destroy_node(): frees a node @val from the nodes hash table.
 150 * Note that node->name is not free'd since it will represent the
 151 * hash table key
 152 */
 153static void destroy_node(void *val)
 154{
 155    QOSGraphNode *node = val;
 156    g_free(node->qemu_name);
 157    g_free(node->command_line);
 158    g_free(node);
 159}
 160
 161/**
 162 * destroy_string(): frees @key from the nodes hash table.
 163 * Actually frees the node->name
 164 */
 165static void destroy_string(void *key)
 166{
 167    g_free(key);
 168}
 169
 170/**
 171 * search_node(): search for a node @key in the nodes hash table
 172 * Returns the QOSGraphNode if found, #NULL otherwise
 173 */
 174static QOSGraphNode *search_node(const char *key)
 175{
 176    return g_hash_table_lookup(node_table, key);
 177}
 178
 179/**
 180 * get_edgelist(): returns the edge list (value) assigned to
 181 * the @key in the edge hash table.
 182 * This list will contain all edges with source equal to @key
 183 *
 184 * Returns: on success: the %QOSGraphEdgeList
 185 *          otherwise: abort()
 186 */
 187static QOSGraphEdgeList *get_edgelist(const char *key)
 188{
 189    return g_hash_table_lookup(edge_table, key);
 190}
 191
 192/**
 193 * search_list_edges(): search for an edge with destination @dest
 194 * in the given @edgelist.
 195 *
 196 * Returns: on success: the %QOSGraphEdge
 197 *          otherwise: #NULL
 198 */
 199static QOSGraphEdge *search_list_edges(QOSGraphEdgeList *edgelist,
 200                                       const char *dest)
 201{
 202    QOSGraphEdge *tmp, *next;
 203    if (!edgelist) {
 204        return NULL;
 205    }
 206    QSLIST_FOREACH_SAFE(tmp, edgelist, edge_list, next) {
 207        if (g_strcmp0(tmp->dest, dest) == 0) {
 208            break;
 209        }
 210    }
 211    return tmp;
 212}
 213
 214/**
 215 * search_machine(): search for a machine @name in the node hash
 216 * table. A machine is the child of the root node.
 217 * This function forces the research in the childs of the root,
 218 * to check the node is a proper machine
 219 *
 220 * Returns: on success: the %QOSGraphNode
 221 *          otherwise: #NULL
 222 */
 223static QOSGraphNode *search_machine(const char *name)
 224{
 225    QOSGraphNode *n;
 226    QOSGraphEdgeList *root_list = get_edgelist(QOS_ROOT);
 227    QOSGraphEdge *e = search_list_edges(root_list, name);
 228    if (!e) {
 229        return NULL;
 230    }
 231    n = search_node(e->dest);
 232    if (n->type == QNODE_MACHINE) {
 233        return n;
 234    }
 235    return NULL;
 236}
 237
 238/**
 239 * create_interface(): checks if there is already
 240 * a node @node in the node hash table, if not
 241 * creates a node @node of type #QNODE_INTERFACE
 242 * and inserts it. If there is one, check it's
 243 * a #QNODE_INTERFACE and abort() if it's not.
 244 */
 245static void create_interface(const char *node)
 246{
 247    QOSGraphNode *interface;
 248    interface = search_node(node);
 249    if (!interface) {
 250        create_node(node, QNODE_INTERFACE);
 251    } else if (interface->type != QNODE_INTERFACE) {
 252        fprintf(stderr, "Error: Node %s is not an interface\n", node);
 253        abort();
 254    }
 255}
 256
 257/**
 258 * build_machine_cmd_line(): builds the command line for the machine
 259 * @node. The node name must be a valid qemu identifier, since it
 260 * will be used to build the command line.
 261 *
 262 * It is also possible to pass an optional @args that will be
 263 * concatenated to the command line.
 264 *
 265 * For machines, prepend -M to the machine name. ", @rgs" is added
 266 * after the -M <machine> command.
 267 */
 268static void build_machine_cmd_line(QOSGraphNode *node, const char *args)
 269{
 270    char *machine = qos_get_machine_type(node->name);
 271    if (args) {
 272        node->command_line = g_strconcat("-M ", machine, ",", args, NULL);
 273    } else {
 274        node->command_line = g_strconcat("-M ", machine, " ", NULL);
 275    }
 276}
 277
 278/**
 279 * build_driver_cmd_line(): builds the command line for the driver
 280 * @node. The node name must be a valid qemu identifier, since it
 281 * will be used to build the command line.
 282 *
 283 * Driver do not need additional command line, since it will be
 284 * provided by the edge options.
 285 *
 286 * For drivers, prepend -device to the node name.
 287 */
 288static void build_driver_cmd_line(QOSGraphNode *node)
 289{
 290    const char *name = node->qemu_name ?: node->name;
 291    node->command_line = g_strconcat(" -device ", name, NULL);
 292}
 293
 294/* qos_print_cb(): callback prints all path found by the DFS algorithm. */
 295static void qos_print_cb(QOSGraphNode *path, int length)
 296{
 297    #if QGRAPH_PRINT_DEBUG
 298        printf("%d elements\n", length);
 299
 300        if (!path) {
 301            return;
 302        }
 303
 304        while (path->path_edge) {
 305            printf("%s ", path->name);
 306            switch (path->path_edge->type) {
 307            case QEDGE_PRODUCES:
 308                printf("--PRODUCES--> ");
 309                break;
 310            case QEDGE_CONSUMED_BY:
 311                printf("--CONSUMED_BY--> ");
 312                break;
 313            case QEDGE_CONTAINS:
 314                printf("--CONTAINS--> ");
 315                break;
 316            }
 317            path = search_node(path->path_edge->dest);
 318        }
 319
 320        printf("%s\n\n", path->name);
 321    #endif
 322}
 323
 324/* qos_push(): push a node @el and edge @e in the qos_node_stack */
 325static void qos_push(QOSGraphNode *el, QOSStackElement *parent,
 326                     QOSGraphEdge *e)
 327{
 328    int len = 0; /* root is not counted */
 329    if (qos_node_tos == QOS_PATH_MAX_ELEMENT_SIZE) {
 330        g_printerr("QOSStack: full stack, cannot push");
 331        abort();
 332    }
 333
 334    if (parent) {
 335        len = parent->length + 1;
 336    }
 337    qos_node_stack[qos_node_tos++] = (QOSStackElement) {
 338        .node = el,
 339        .parent = parent,
 340        .parent_edge = e,
 341        .length = len,
 342    };
 343}
 344
 345/* qos_tos(): returns the top of stack, without popping */
 346static QOSStackElement *qos_tos(void)
 347{
 348    return &qos_node_stack[qos_node_tos - 1];
 349}
 350
 351/* qos_pop(): pops an element from the tos, setting it unvisited*/
 352static QOSStackElement *qos_pop(void)
 353{
 354    if (qos_node_tos == 0) {
 355        g_printerr("QOSStack: empty stack, cannot pop");
 356        abort();
 357    }
 358    QOSStackElement *e = qos_tos();
 359    e->node->visited = false;
 360    qos_node_tos--;
 361    return e;
 362}
 363
 364/**
 365 * qos_reverse_path(): reverses the found path, going from
 366 * test-to-machine to machine-to-test
 367 */
 368static QOSGraphNode *qos_reverse_path(QOSStackElement *el)
 369{
 370    if (!el) {
 371        return NULL;
 372    }
 373
 374    el->node->path_edge = NULL;
 375
 376    while (el->parent) {
 377        el->parent->node->path_edge = el->parent_edge;
 378        el = el->parent;
 379    }
 380
 381    return el->node;
 382}
 383
 384/**
 385 * qos_traverse_graph(): graph-walking algorithm, using Depth First Search it
 386 * starts from the root @machine and walks all possible path until it
 387 * reaches a test node.
 388 * At that point, it reverses the path found and invokes the @callback.
 389 *
 390 * Being Depth First Search, time complexity is O(|V| + |E|), while
 391 * space is O(|V|). In this case, the maximum stack size is set by
 392 * QOS_PATH_MAX_ELEMENT_SIZE.
 393 */
 394static void qos_traverse_graph(QOSGraphNode *root, QOSTestCallback callback)
 395{
 396    QOSGraphNode *v, *dest_node, *path;
 397    QOSStackElement *s_el;
 398    QOSGraphEdge *e, *next;
 399    QOSGraphEdgeList *list;
 400
 401    qos_push(root, NULL, NULL);
 402
 403    while (qos_node_tos > 0) {
 404        s_el = qos_tos();
 405        v = s_el->node;
 406        if (v->visited) {
 407            qos_pop();
 408            continue;
 409        }
 410        v->visited = true;
 411        list = get_edgelist(v->name);
 412        if (!list) {
 413            qos_pop();
 414            if (v->type == QNODE_TEST) {
 415                v->visited = false;
 416                path = qos_reverse_path(s_el);
 417                callback(path, s_el->length);
 418            }
 419        } else {
 420            QSLIST_FOREACH_SAFE(e, list, edge_list, next) {
 421                dest_node = search_node(e->dest);
 422
 423                if (!dest_node) {
 424                    fprintf(stderr, "node %s in %s -> %s does not exist\n",
 425                            e->dest, v->name, e->dest);
 426                    abort();
 427                }
 428
 429                if (!dest_node->visited && dest_node->available) {
 430                    qos_push(dest_node, s_el, e);
 431                }
 432            }
 433        }
 434    }
 435}
 436
 437/* QGRAPH API*/
 438
 439QOSGraphNode *qos_graph_get_node(const char *key)
 440{
 441    return search_node(key);
 442}
 443
 444bool qos_graph_has_node(const char *node)
 445{
 446    QOSGraphNode *n = search_node(node);
 447    return n != NULL;
 448}
 449
 450QOSNodeType qos_graph_get_node_type(const char *node)
 451{
 452    QOSGraphNode *n = search_node(node);
 453    if (n) {
 454        return n->type;
 455    }
 456    return -1;
 457}
 458
 459bool qos_graph_get_node_availability(const char *node)
 460{
 461    QOSGraphNode *n = search_node(node);
 462    if (n) {
 463        return n->available;
 464    }
 465    return false;
 466}
 467
 468QOSGraphEdge *qos_graph_get_edge(const char *node, const char *dest)
 469{
 470    QOSGraphEdgeList *list = get_edgelist(node);
 471    return search_list_edges(list, dest);
 472}
 473
 474QOSEdgeType qos_graph_edge_get_type(QOSGraphEdge *edge)
 475{
 476    if (!edge) {
 477        return -1;
 478    }
 479    return edge->type;
 480}
 481
 482char *qos_graph_edge_get_dest(QOSGraphEdge *edge)
 483{
 484    if (!edge) {
 485        return NULL;
 486    }
 487    return edge->dest;
 488}
 489
 490void *qos_graph_edge_get_arg(QOSGraphEdge *edge)
 491{
 492    if (!edge) {
 493        return NULL;
 494    }
 495    return edge->arg;
 496}
 497
 498char *qos_graph_edge_get_after_cmd_line(QOSGraphEdge *edge)
 499{
 500    if (!edge) {
 501        return NULL;
 502    }
 503    return edge->after_cmd_line;
 504}
 505
 506char *qos_graph_edge_get_before_cmd_line(QOSGraphEdge *edge)
 507{
 508    if (!edge) {
 509        return NULL;
 510    }
 511    return edge->before_cmd_line;
 512}
 513
 514char *qos_graph_edge_get_extra_device_opts(QOSGraphEdge *edge)
 515{
 516    if (!edge) {
 517        return NULL;
 518    }
 519    return edge->extra_device_opts;
 520}
 521
 522char *qos_graph_edge_get_name(QOSGraphEdge *edge)
 523{
 524    if (!edge) {
 525        return NULL;
 526    }
 527    return edge->edge_name;
 528}
 529
 530bool qos_graph_has_edge(const char *start, const char *dest)
 531{
 532    QOSGraphEdgeList *list = get_edgelist(start);
 533    QOSGraphEdge *e = search_list_edges(list, dest);
 534    return e != NULL;
 535}
 536
 537QOSGraphNode *qos_graph_get_machine(const char *node)
 538{
 539    return search_machine(node);
 540}
 541
 542bool qos_graph_has_machine(const char *node)
 543{
 544    QOSGraphNode *m = search_machine(node);
 545    return m != NULL;
 546}
 547
 548void qos_print_graph(void)
 549{
 550    qos_graph_foreach_test_path(qos_print_cb);
 551}
 552
 553void qos_graph_init(void)
 554{
 555    if (!node_table) {
 556        node_table = g_hash_table_new_full(g_str_hash, g_str_equal,
 557                                           destroy_string, destroy_node);
 558        create_node(QOS_ROOT, QNODE_DRIVER);
 559    }
 560
 561    if (!edge_table) {
 562        edge_table = g_hash_table_new_full(g_str_hash, g_str_equal,
 563                                           destroy_string, destroy_edges);
 564    }
 565}
 566
 567void qos_graph_destroy(void)
 568{
 569    if (node_table) {
 570        g_hash_table_destroy(node_table);
 571    }
 572
 573    if (edge_table) {
 574        g_hash_table_destroy(edge_table);
 575    }
 576
 577    node_table = NULL;
 578    edge_table = NULL;
 579}
 580
 581void qos_node_destroy(void *key)
 582{
 583    g_hash_table_remove(node_table, key);
 584}
 585
 586void qos_edge_destroy(void *key)
 587{
 588    g_hash_table_remove(edge_table, key);
 589}
 590
 591void qos_add_test(const char *name, const char *interface,
 592                  QOSTestFunc test_func, QOSGraphTestOptions *opts)
 593{
 594    QOSGraphNode *node;
 595    char *test_name = g_strdup_printf("%s-tests/%s", interface, name);
 596    QOSGraphTestOptions def_opts = { };
 597
 598    if (!opts) {
 599        opts = &def_opts;
 600    }
 601    node = create_node(test_name, QNODE_TEST);
 602    node->u.test.function = test_func;
 603    node->u.test.arg = opts->arg;
 604    assert(!opts->edge.arg);
 605    assert(!opts->edge.size_arg);
 606
 607    node->u.test.before = opts->before;
 608    node->u.test.subprocess = opts->subprocess;
 609    node->available = true;
 610    add_edge(interface, test_name, QEDGE_CONSUMED_BY, &opts->edge);
 611    g_free(test_name);
 612}
 613
 614void qos_node_create_machine(const char *name, QOSCreateMachineFunc function)
 615{
 616    qos_node_create_machine_args(name, function, NULL);
 617}
 618
 619void qos_node_create_machine_args(const char *name,
 620                                  QOSCreateMachineFunc function,
 621                                  const char *opts)
 622{
 623    QOSGraphNode *node = create_node(name, QNODE_MACHINE);
 624    build_machine_cmd_line(node, opts);
 625    node->u.machine.constructor = function;
 626    add_edge(QOS_ROOT, name, QEDGE_CONTAINS, NULL);
 627}
 628
 629void qos_node_create_driver(const char *name, QOSCreateDriverFunc function)
 630{
 631    QOSGraphNode *node = create_node(name, QNODE_DRIVER);
 632    build_driver_cmd_line(node);
 633    node->u.driver.constructor = function;
 634}
 635
 636void qos_node_create_driver_named(const char *name, const char *qemu_name,
 637                                  QOSCreateDriverFunc function)
 638{
 639    QOSGraphNode *node = create_node(name, QNODE_DRIVER);
 640    node->qemu_name = g_strdup(qemu_name);
 641    build_driver_cmd_line(node);
 642    node->u.driver.constructor = function;
 643}
 644
 645void qos_node_contains(const char *container, const char *contained,
 646                       QOSGraphEdgeOptions *opts, ...)
 647{
 648    va_list va;
 649
 650    if (opts == NULL) {
 651        add_edge(container, contained, QEDGE_CONTAINS, NULL);
 652        return;
 653    }
 654
 655    va_start(va, opts);
 656    do {
 657        add_edge(container, contained, QEDGE_CONTAINS, opts);
 658        opts = va_arg(va, QOSGraphEdgeOptions *);
 659    } while (opts != NULL);
 660
 661    va_end(va);
 662}
 663
 664void qos_node_produces(const char *producer, const char *interface)
 665{
 666    create_interface(interface);
 667    add_edge(producer, interface, QEDGE_PRODUCES, NULL);
 668}
 669
 670void qos_node_consumes(const char *consumer, const char *interface,
 671                       QOSGraphEdgeOptions *opts)
 672{
 673    create_interface(interface);
 674    add_edge(interface, consumer, QEDGE_CONSUMED_BY, opts);
 675}
 676
 677static void qos_graph_node_set_availability_explicit(const char *node, bool av)
 678{
 679    QOSGraphEdgeList *elist;
 680    QOSGraphNode *n = search_node(node);
 681    QOSGraphEdge *e, *next;
 682    if (!n) {
 683        return;
 684    }
 685    n->available = av;
 686    elist = get_edgelist(node);
 687    if (!elist) {
 688        return;
 689    }
 690    QSLIST_FOREACH_SAFE(e, elist, edge_list, next) {
 691        if (e->type == QEDGE_CONTAINS || e->type == QEDGE_PRODUCES) {
 692            qos_graph_node_set_availability_explicit(e->dest, av);
 693        }
 694    }
 695}
 696
 697/*
 698 * Behaves as qos_graph_node_set_availability_explicit(), except that the
 699 * former always matches by node name only, whereas this function matches both
 700 * by node name and node's optional 'qemu_name' field.
 701 */
 702void qos_graph_node_set_availability(const char *node, bool av)
 703{
 704    GList *l;
 705    QOSGraphEdgeList *elist;
 706    QOSGraphEdge *e, *next;
 707    QOSGraphNode *n;
 708    GList *keys = g_hash_table_get_keys(node_table);
 709
 710    for (l = keys; l != NULL; l = l->next) {
 711        const gchar *key = l->data;
 712        n = g_hash_table_lookup(node_table, key);
 713        /*
 714         * node's 'qemu_name' is set if there is more than one device with
 715         * the same QEMU (QMP) device name
 716         */
 717        const char *node_name = n->qemu_name ?: n->name;
 718        if (g_strcmp0(node_name, node) == 0) {
 719            n->available = av;
 720            elist = get_edgelist(n->name);
 721            if (elist) {
 722                QSLIST_FOREACH_SAFE(e, elist, edge_list, next) {
 723                    if (e->type == QEDGE_CONTAINS || e->type == QEDGE_PRODUCES)
 724                    {
 725                        qos_graph_node_set_availability_explicit(e->dest, av);
 726                    }
 727                }
 728            }
 729        }
 730    }
 731    g_list_free(keys);
 732}
 733
 734void qos_graph_foreach_test_path(QOSTestCallback fn)
 735{
 736    QOSGraphNode *root = qos_graph_get_node(QOS_ROOT);
 737    qos_traverse_graph(root, fn);
 738}
 739
 740QOSGraphObject *qos_machine_new(QOSGraphNode *node, QTestState *qts)
 741{
 742    QOSGraphObject *obj;
 743
 744    g_assert(node->type == QNODE_MACHINE);
 745    obj = node->u.machine.constructor(qts);
 746    obj->free = g_free;
 747    return obj;
 748}
 749
 750QOSGraphObject *qos_driver_new(QOSGraphNode *node, QOSGraphObject *parent,
 751                               QGuestAllocator *alloc, void *arg)
 752{
 753    QOSGraphObject *obj;
 754
 755    g_assert(node->type == QNODE_DRIVER);
 756    obj = node->u.driver.constructor(parent, alloc, arg);
 757    obj->free = g_free;
 758    return obj;
 759}
 760
 761void qos_object_destroy(QOSGraphObject *obj)
 762{
 763    if (!obj) {
 764        return;
 765    }
 766    if (obj->destructor) {
 767        obj->destructor(obj);
 768    }
 769    if (obj->free) {
 770        obj->free(obj);
 771    }
 772}
 773
 774void qos_object_queue_destroy(QOSGraphObject *obj)
 775{
 776    g_test_queue_destroy((GDestroyNotify) qos_object_destroy, obj);
 777}
 778
 779void qos_object_start_hw(QOSGraphObject *obj)
 780{
 781    if (obj->start_hw) {
 782        obj->start_hw(obj);
 783    }
 784}
 785
 786char *qos_get_machine_type(char *name)
 787{
 788    while (*name != '\0' && *name != '/') {
 789        name++;
 790    }
 791
 792    if (!*name || !name[1]) {
 793        fprintf(stderr, "Machine name has to be of the form <arch>/<machine>\n");
 794        abort();
 795    }
 796
 797    return name + 1;
 798}
 799
 800void qos_delete_cmd_line(const char *name)
 801{
 802    QOSGraphNode *node = search_node(name);
 803    if (node) {
 804        g_free(node->command_line);
 805        node->command_line = NULL;
 806    }
 807}
 808
 809void qos_dump_graph(void)
 810{
 811    GList *keys;
 812    GList *l;
 813    QOSGraphEdgeList *list;
 814    QOSGraphEdge *e, *next;
 815    QOSGraphNode *dest_node, *node;
 816
 817    qos_printf("ALL QGRAPH EDGES: {\n");
 818    keys = g_hash_table_get_keys(edge_table);
 819    for (l = keys; l != NULL; l = l->next) {
 820        const gchar *key = l->data;
 821        qos_printf("\t src='%s'\n", key);
 822        list = get_edgelist(key);
 823        QSLIST_FOREACH_SAFE(e, list, edge_list, next) {
 824            dest_node = g_hash_table_lookup(node_table, e->dest);
 825            qos_printf("\t\t|-> dest='%s' type=%d (node=%p)",
 826                       e->dest, e->type, dest_node);
 827            if (!dest_node) {
 828                qos_printf_literal(" <------- ERROR !");
 829            }
 830            qos_printf_literal("\n");
 831        }
 832    }
 833    g_list_free(keys);
 834    qos_printf("}\n");
 835
 836    qos_printf("ALL QGRAPH NODES: {\n");
 837    keys = g_hash_table_get_keys(node_table);
 838    for (l = keys; l != NULL; l = l->next) {
 839        const gchar *key = l->data;
 840        node = g_hash_table_lookup(node_table, key);
 841        qos_printf("\t name='%s' ", key);
 842        if (node->qemu_name) {
 843            qos_printf_literal("qemu_name='%s' ", node->qemu_name);
 844        }
 845        qos_printf_literal("type=%d cmd_line='%s' [%s]\n",
 846                           node->type, node->command_line,
 847                           node->available ? "available" : "UNAVAILABLE"
 848        );
 849    }
 850    g_list_free(keys);
 851    qos_printf("}\n");
 852}
 853