tests/qtest/libqos/qgraph.c

   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 ""
  27 typedef struct QOSStackElement QOSStackElement;
  28
  29 /* Graph Edge.*/
  30 struct 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
  44 typedef QSLIST_HEAD(, QOSGraphEdge) QOSGraphEdgeList;
  45
  46 /**
  47  * Stack used to keep track of the discovered path when using
  48  * the DFS algorithm
  49  */
  50 struct QOSStackElement {
  51     QOSGraphNode *node;
  52     QOSStackElement *parent;
  53     QOSGraphEdge *parent_edge;
  54     int length;
  55 };
  56
  57 /* Each entry in these hash table will consist of <string, node/edge> pair. */
  58 static GHashTable *edge_table;
  59 static GHashTable *node_table;
  60
  61 /* stack used by the DFS algorithm to store the path from machine to test */
  62 static QOSStackElement qos_node_stack[QOS_PATH_MAX_ELEMENT_SIZE];
  63 static 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  */
  75 static 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 */
 109 static 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  */
 133 static 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  */
 153 static 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  */
 165 static 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  */
 174 static 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  */
 187 static 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  */
 199 static 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 children of the root,
 218  * to check the node is a proper machine
 219  *
 220  * Returns: on success: the %QOSGraphNode
 221  *          otherwise: #NULL
 222  */
 223 static 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  */
 245 static 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  */
 268 static 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  */
 288 static 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. */
 295 static 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 */
 325 static 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 */
 346 static 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*/
 352 static 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  */
 368 static 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  */
 394 static 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
 439 QOSGraphNode *qos_graph_get_node(const char *key)
 440 {
 441     return search_node(key);
 442 }
 443
 444 bool qos_graph_has_node(const char *node)
 445 {
 446     QOSGraphNode *n = search_node(node);
 447     return n != NULL;
 448 }
 449
 450 QOSNodeType 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
 459 bool 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
 468 QOSGraphEdge *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
 474 QOSEdgeType qos_graph_edge_get_type(QOSGraphEdge *edge)
 475 {
 476     if (!edge) {
 477         return -1;
 478     }
 479     return edge->type;
 480 }
 481
 482 char *qos_graph_edge_get_dest(QOSGraphEdge *edge)
 483 {
 484     if (!edge) {
 485         return NULL;
 486     }
 487     return edge->dest;
 488 }
 489
 490 void *qos_graph_edge_get_arg(QOSGraphEdge *edge)
 491 {
 492     if (!edge) {
 493         return NULL;
 494     }
 495     return edge->arg;
 496 }
 497
 498 char *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
 506 char *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
 514 char *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
 522 char *qos_graph_edge_get_name(QOSGraphEdge *edge)
 523 {
 524     if (!edge) {
 525         return NULL;
 526     }
 527     return edge->edge_name;
 528 }
 529
 530 bool 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
 537 QOSGraphNode *qos_graph_get_machine(const char *node)
 538 {
 539     return search_machine(node);
 540 }
 541
 542 bool qos_graph_has_machine(const char *node)
 543 {
 544     QOSGraphNode *m = search_machine(node);
 545     return m != NULL;
 546 }
 547
 548 void qos_print_graph(void)
 549 {
 550     qos_graph_foreach_test_path(qos_print_cb);
 551 }
 552
 553 void 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
 567 void 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
 581 void qos_node_destroy(void *key)
 582 {
 583     g_hash_table_remove(node_table, key);
 584 }
 585
 586 void qos_edge_destroy(void *key)
 587 {
 588     g_hash_table_remove(edge_table, key);
 589 }
 590
 591 void 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
 614 void qos_node_create_machine(const char *name, QOSCreateMachineFunc function)
 615 {
 616     qos_node_create_machine_args(name, function, NULL);
 617 }
 618
 619 void 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
 629 void 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
 636 void 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
 645 void 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
 664 void qos_node_produces(const char *producer, const char *interface)
 665 {
 666     create_interface(interface);
 667     add_edge(producer, interface, QEDGE_PRODUCES, NULL);
 668 }
 669
 670 void 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
 677 static 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  */
 702 void 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
 734 void 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
 740 QOSGraphObject *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
 750 QOSGraphObject *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
 761 void 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
 774 void qos_object_queue_destroy(QOSGraphObject *obj)
 775 {
 776     g_test_queue_destroy((GDestroyNotify) qos_object_destroy, obj);
 777 }
 778
 779 void qos_object_start_hw(QOSGraphObject *obj)
 780 {
 781     if (obj->start_hw) {
 782         obj->start_hw(obj);
 783     }
 784 }
 785
 786 char *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
 800 void 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
 809 void 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 }