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 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 "libqos/qgraph_internal.h"
  23#include "libqos/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_memdup(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->command_line);
 157    g_free(node);
 158}
 159
 160/**
 161 * destroy_string(): frees @key from the nodes hash table.
 162 * Actually frees the node->name
 163 */
 164static void destroy_string(void *key)
 165{
 166    g_free(key);
 167}
 168
 169/**
 170 * search_node(): search for a node @key in the nodes hash table
 171 * Returns the QOSGraphNode if found, #NULL otherwise
 172 */
 173static QOSGraphNode *search_node(const char *key)
 174{
 175    return g_hash_table_lookup(node_table, key);
 176}
 177
 178/**
 179 * get_edgelist(): returns the edge list (value) assigned to
 180 * the @key in the edge hash table.
 181 * This list will contain all edges with source equal to @key
 182 *
 183 * Returns: on success: the %QOSGraphEdgeList
 184 *          otherwise: abort()
 185 */
 186static QOSGraphEdgeList *get_edgelist(const char *key)
 187{
 188    return g_hash_table_lookup(edge_table, key);
 189}
 190
 191/**
 192 * search_list_edges(): search for an edge with destination @dest
 193 * in the given @edgelist.
 194 *
 195 * Returns: on success: the %QOSGraphEdge
 196 *          otherwise: #NULL
 197 */
 198static QOSGraphEdge *search_list_edges(QOSGraphEdgeList *edgelist,
 199                                       const char *dest)
 200{
 201    QOSGraphEdge *tmp, *next;
 202    if (!edgelist) {
 203        return NULL;
 204    }
 205    QSLIST_FOREACH_SAFE(tmp, edgelist, edge_list, next) {
 206        if (g_strcmp0(tmp->dest, dest) == 0) {
 207            break;
 208        }
 209    }
 210    return tmp;
 211}
 212
 213/**
 214 * search_machine(): search for a machine @name in the node hash
 215 * table. A machine is the child of the root node.
 216 * This function forces the research in the childs of the root,
 217 * to check the node is a proper machine
 218 *
 219 * Returns: on success: the %QOSGraphNode
 220 *          otherwise: #NULL
 221 */
 222static QOSGraphNode *search_machine(const char *name)
 223{
 224    QOSGraphNode *n;
 225    QOSGraphEdgeList *root_list = get_edgelist(QOS_ROOT);
 226    QOSGraphEdge *e = search_list_edges(root_list, name);
 227    if (!e) {
 228        return NULL;
 229    }
 230    n = search_node(e->dest);
 231    if (n->type == QNODE_MACHINE) {
 232        return n;
 233    }
 234    return NULL;
 235}
 236
 237/**
 238 * create_interface(): checks if there is already
 239 * a node @node in the node hash table, if not
 240 * creates a node @node of type #QNODE_INTERFACE
 241 * and inserts it. If there is one, check it's
 242 * a #QNODE_INTERFACE and abort() if it's not.
 243 */
 244static void create_interface(const char *node)
 245{
 246    QOSGraphNode *interface;
 247    interface = search_node(node);
 248    if (!interface) {
 249        create_node(node, QNODE_INTERFACE);
 250    } else if (interface->type != QNODE_INTERFACE) {
 251        fprintf(stderr, "Error: Node %s is not an interface\n", node);
 252        abort();
 253    }
 254}
 255
 256/**
 257 * build_machine_cmd_line(): builds the command line for the machine
 258 * @node. The node name must be a valid qemu identifier, since it
 259 * will be used to build the command line.
 260 *
 261 * It is also possible to pass an optional @args that will be
 262 * concatenated to the command line.
 263 *
 264 * For machines, prepend -M to the machine name. ", @rgs" is added
 265 * after the -M <machine> command.
 266 */
 267static void build_machine_cmd_line(QOSGraphNode *node, const char *args)
 268{
 269    char *machine = qos_get_machine_type(node->name);
 270    if (args) {
 271        node->command_line = g_strconcat("-M ", machine, ",", args, NULL);
 272    } else {
 273        node->command_line = g_strconcat("-M ", machine, " ", NULL);
 274    }
 275}
 276
 277/**
 278 * build_driver_cmd_line(): builds the command line for the driver
 279 * @node. The node name must be a valid qemu identifier, since it
 280 * will be used to build the command line.
 281 *
 282 * Driver do not need additional command line, since it will be
 283 * provided by the edge options.
 284 *
 285 * For drivers, prepend -device to the node name.
 286 */
 287static void build_driver_cmd_line(QOSGraphNode *node)
 288{
 289    node->command_line = g_strconcat(" -device ", node->name, NULL);
 290}
 291
 292/* qos_print_cb(): callback prints all path found by the DFS algorithm. */
 293static void qos_print_cb(QOSGraphNode *path, int length)
 294{
 295    #if QGRAPH_PRINT_DEBUG
 296        printf("%d elements\n", length);
 297
 298        if (!path) {
 299            return;
 300        }
 301
 302        while (path->path_edge) {
 303            printf("%s ", path->name);
 304            switch (path->path_edge->type) {
 305            case QEDGE_PRODUCES:
 306                printf("--PRODUCES--> ");
 307                break;
 308            case QEDGE_CONSUMED_BY:
 309                printf("--CONSUMED_BY--> ");
 310                break;
 311            case QEDGE_CONTAINS:
 312                printf("--CONTAINS--> ");
 313                break;
 314            }
 315            path = search_node(path->path_edge->dest);
 316        }
 317
 318        printf("%s\n\n", path->name);
 319    #endif
 320}
 321
 322/* qos_push(): push a node @el and edge @e in the qos_node_stack */
 323static void qos_push(QOSGraphNode *el, QOSStackElement *parent,
 324                     QOSGraphEdge *e)
 325{
 326    int len = 0; /* root is not counted */
 327    if (qos_node_tos == QOS_PATH_MAX_ELEMENT_SIZE) {
 328        g_printerr("QOSStack: full stack, cannot push");
 329        abort();
 330    }
 331
 332    if (parent) {
 333        len = parent->length + 1;
 334    }
 335    qos_node_stack[qos_node_tos++] = (QOSStackElement) {
 336        .node = el,
 337        .parent = parent,
 338        .parent_edge = e,
 339        .length = len,
 340    };
 341}
 342
 343/* qos_tos(): returns the top of stack, without popping */
 344static QOSStackElement *qos_tos(void)
 345{
 346    return &qos_node_stack[qos_node_tos - 1];
 347}
 348
 349/* qos_pop(): pops an element from the tos, setting it unvisited*/
 350static QOSStackElement *qos_pop(void)
 351{
 352    if (qos_node_tos == 0) {
 353        g_printerr("QOSStack: empty stack, cannot pop");
 354        abort();
 355    }
 356    QOSStackElement *e = qos_tos();
 357    e->node->visited = false;
 358    qos_node_tos--;
 359    return e;
 360}
 361
 362/**
 363 * qos_reverse_path(): reverses the found path, going from
 364 * test-to-machine to machine-to-test
 365 */
 366static QOSGraphNode *qos_reverse_path(QOSStackElement *el)
 367{
 368    if (!el) {
 369        return NULL;
 370    }
 371
 372    el->node->path_edge = NULL;
 373
 374    while (el->parent) {
 375        el->parent->node->path_edge = el->parent_edge;
 376        el = el->parent;
 377    }
 378
 379    return el->node;
 380}
 381
 382/**
 383 * qos_traverse_graph(): graph-walking algorithm, using Depth First Search it
 384 * starts from the root @machine and walks all possible path until it
 385 * reaches a test node.
 386 * At that point, it reverses the path found and invokes the @callback.
 387 *
 388 * Being Depth First Search, time complexity is O(|V| + |E|), while
 389 * space is O(|V|). In this case, the maximum stack size is set by
 390 * QOS_PATH_MAX_ELEMENT_SIZE.
 391 */
 392static void qos_traverse_graph(QOSGraphNode *root, QOSTestCallback callback)
 393{
 394    QOSGraphNode *v, *dest_node, *path;
 395    QOSStackElement *s_el;
 396    QOSGraphEdge *e, *next;
 397    QOSGraphEdgeList *list;
 398
 399    qos_push(root, NULL, NULL);
 400
 401    while (qos_node_tos > 0) {
 402        s_el = qos_tos();
 403        v = s_el->node;
 404        if (v->visited) {
 405            qos_pop();
 406            continue;
 407        }
 408        v->visited = true;
 409        list = get_edgelist(v->name);
 410        if (!list) {
 411            qos_pop();
 412            if (v->type == QNODE_TEST) {
 413                v->visited = false;
 414                path = qos_reverse_path(s_el);
 415                callback(path, s_el->length);
 416            }
 417        } else {
 418            QSLIST_FOREACH_SAFE(e, list, edge_list, next) {
 419                dest_node = search_node(e->dest);
 420
 421                if (!dest_node) {
 422                    fprintf(stderr, "node %s in %s -> %s does not exist\n",
 423                            e->dest, v->name, e->dest);
 424                    abort();
 425                }
 426
 427                if (!dest_node->visited && dest_node->available) {
 428                    qos_push(dest_node, s_el, e);
 429                }
 430            }
 431        }
 432    }
 433}
 434
 435/* QGRAPH API*/
 436
 437QOSGraphNode *qos_graph_get_node(const char *key)
 438{
 439    return search_node(key);
 440}
 441
 442bool qos_graph_has_node(const char *node)
 443{
 444    QOSGraphNode *n = search_node(node);
 445    return n != NULL;
 446}
 447
 448QOSNodeType qos_graph_get_node_type(const char *node)
 449{
 450    QOSGraphNode *n = search_node(node);
 451    if (n) {
 452        return n->type;
 453    }
 454    return -1;
 455}
 456
 457bool qos_graph_get_node_availability(const char *node)
 458{
 459    QOSGraphNode *n = search_node(node);
 460    if (n) {
 461        return n->available;
 462    }
 463    return false;
 464}
 465
 466QOSGraphEdge *qos_graph_get_edge(const char *node, const char *dest)
 467{
 468    QOSGraphEdgeList *list = get_edgelist(node);
 469    return search_list_edges(list, dest);
 470}
 471
 472QOSEdgeType qos_graph_edge_get_type(QOSGraphEdge *edge)
 473{
 474    if (!edge) {
 475        return -1;
 476    }
 477    return edge->type;
 478}
 479
 480char *qos_graph_edge_get_dest(QOSGraphEdge *edge)
 481{
 482    if (!edge) {
 483        return NULL;
 484    }
 485    return edge->dest;
 486}
 487
 488void *qos_graph_edge_get_arg(QOSGraphEdge *edge)
 489{
 490    if (!edge) {
 491        return NULL;
 492    }
 493    return edge->arg;
 494}
 495
 496char *qos_graph_edge_get_after_cmd_line(QOSGraphEdge *edge)
 497{
 498    if (!edge) {
 499        return NULL;
 500    }
 501    return edge->after_cmd_line;
 502}
 503
 504char *qos_graph_edge_get_before_cmd_line(QOSGraphEdge *edge)
 505{
 506    if (!edge) {
 507        return NULL;
 508    }
 509    return edge->before_cmd_line;
 510}
 511
 512char *qos_graph_edge_get_extra_device_opts(QOSGraphEdge *edge)
 513{
 514    if (!edge) {
 515        return NULL;
 516    }
 517    return edge->extra_device_opts;
 518}
 519
 520char *qos_graph_edge_get_name(QOSGraphEdge *edge)
 521{
 522    if (!edge) {
 523        return NULL;
 524    }
 525    return edge->edge_name;
 526}
 527
 528bool qos_graph_has_edge(const char *start, const char *dest)
 529{
 530    QOSGraphEdgeList *list = get_edgelist(start);
 531    QOSGraphEdge *e = search_list_edges(list, dest);
 532    return e != NULL;
 533}
 534
 535QOSGraphNode *qos_graph_get_machine(const char *node)
 536{
 537    return search_machine(node);
 538}
 539
 540bool qos_graph_has_machine(const char *node)
 541{
 542    QOSGraphNode *m = search_machine(node);
 543    return m != NULL;
 544}
 545
 546void qos_print_graph(void)
 547{
 548    qos_graph_foreach_test_path(qos_print_cb);
 549}
 550
 551void qos_graph_init(void)
 552{
 553    if (!node_table) {
 554        node_table = g_hash_table_new_full(g_str_hash, g_str_equal,
 555                                           destroy_string, destroy_node);
 556        create_node(QOS_ROOT, QNODE_DRIVER);
 557    }
 558
 559    if (!edge_table) {
 560        edge_table = g_hash_table_new_full(g_str_hash, g_str_equal,
 561                                           destroy_string, destroy_edges);
 562    }
 563}
 564
 565void qos_graph_destroy(void)
 566{
 567    if (node_table) {
 568        g_hash_table_destroy(node_table);
 569    }
 570
 571    if (edge_table) {
 572        g_hash_table_destroy(edge_table);
 573    }
 574
 575    node_table = NULL;
 576    edge_table = NULL;
 577}
 578
 579void qos_node_destroy(void *key)
 580{
 581    g_hash_table_remove(node_table, key);
 582}
 583
 584void qos_edge_destroy(void *key)
 585{
 586    g_hash_table_remove(edge_table, key);
 587}
 588
 589void qos_add_test(const char *name, const char *interface,
 590                  QOSTestFunc test_func, QOSGraphTestOptions *opts)
 591{
 592    QOSGraphNode *node;
 593    char *test_name = g_strdup_printf("%s-tests/%s", interface, name);
 594    QOSGraphTestOptions def_opts = { };
 595
 596    if (!opts) {
 597        opts = &def_opts;
 598    }
 599    node = create_node(test_name, QNODE_TEST);
 600    node->u.test.function = test_func;
 601    node->u.test.arg = opts->arg;
 602    assert(!opts->edge.arg);
 603    assert(!opts->edge.size_arg);
 604
 605    node->u.test.before = opts->before;
 606    node->u.test.subprocess = opts->subprocess;
 607    node->available = true;
 608    add_edge(interface, test_name, QEDGE_CONSUMED_BY, &opts->edge);
 609    g_free(test_name);
 610}
 611
 612void qos_node_create_machine(const char *name, QOSCreateMachineFunc function)
 613{
 614    qos_node_create_machine_args(name, function, NULL);
 615}
 616
 617void qos_node_create_machine_args(const char *name,
 618                                  QOSCreateMachineFunc function,
 619                                  const char *opts)
 620{
 621    QOSGraphNode *node = create_node(name, QNODE_MACHINE);
 622    build_machine_cmd_line(node, opts);
 623    node->u.machine.constructor = function;
 624    add_edge(QOS_ROOT, name, QEDGE_CONTAINS, NULL);
 625}
 626
 627void qos_node_create_driver(const char *name, QOSCreateDriverFunc function)
 628{
 629    QOSGraphNode *node = create_node(name, QNODE_DRIVER);
 630    build_driver_cmd_line(node);
 631    node->u.driver.constructor = function;
 632}
 633
 634void qos_node_contains(const char *container, const char *contained,
 635                       QOSGraphEdgeOptions *opts, ...)
 636{
 637    va_list va;
 638
 639    if (opts == NULL) {
 640        add_edge(container, contained, QEDGE_CONTAINS, NULL);
 641        return;
 642    }
 643
 644    va_start(va, opts);
 645    do {
 646        add_edge(container, contained, QEDGE_CONTAINS, opts);
 647        opts = va_arg(va, QOSGraphEdgeOptions *);
 648    } while (opts != NULL);
 649
 650    va_end(va);
 651}
 652
 653void qos_node_produces(const char *producer, const char *interface)
 654{
 655    create_interface(interface);
 656    add_edge(producer, interface, QEDGE_PRODUCES, NULL);
 657}
 658
 659void qos_node_consumes(const char *consumer, const char *interface,
 660                       QOSGraphEdgeOptions *opts)
 661{
 662    create_interface(interface);
 663    add_edge(interface, consumer, QEDGE_CONSUMED_BY, opts);
 664}
 665
 666void qos_graph_node_set_availability(const char *node, bool av)
 667{
 668    QOSGraphEdgeList *elist;
 669    QOSGraphNode *n = search_node(node);
 670    QOSGraphEdge *e, *next;
 671    if (!n) {
 672        return;
 673    }
 674    n->available = av;
 675    elist = get_edgelist(node);
 676    if (!elist) {
 677        return;
 678    }
 679    QSLIST_FOREACH_SAFE(e, elist, edge_list, next) {
 680        if (e->type == QEDGE_CONTAINS || e->type == QEDGE_PRODUCES) {
 681            qos_graph_node_set_availability(e->dest, av);
 682        }
 683    }
 684}
 685
 686void qos_graph_foreach_test_path(QOSTestCallback fn)
 687{
 688    QOSGraphNode *root = qos_graph_get_node(QOS_ROOT);
 689    qos_traverse_graph(root, fn);
 690}
 691
 692QOSGraphObject *qos_machine_new(QOSGraphNode *node, QTestState *qts)
 693{
 694    QOSGraphObject *obj;
 695
 696    g_assert(node->type == QNODE_MACHINE);
 697    obj = node->u.machine.constructor(qts);
 698    obj->free = g_free;
 699    return obj;
 700}
 701
 702QOSGraphObject *qos_driver_new(QOSGraphNode *node, QOSGraphObject *parent,
 703                               QGuestAllocator *alloc, void *arg)
 704{
 705    QOSGraphObject *obj;
 706
 707    g_assert(node->type == QNODE_DRIVER);
 708    obj = node->u.driver.constructor(parent, alloc, arg);
 709    obj->free = g_free;
 710    return obj;
 711}
 712
 713void qos_object_destroy(QOSGraphObject *obj)
 714{
 715    if (!obj) {
 716        return;
 717    }
 718    if (obj->destructor) {
 719        obj->destructor(obj);
 720    }
 721    if (obj->free) {
 722        obj->free(obj);
 723    }
 724}
 725
 726void qos_object_queue_destroy(QOSGraphObject *obj)
 727{
 728    g_test_queue_destroy((GDestroyNotify) qos_object_destroy, obj);
 729}
 730
 731void qos_object_start_hw(QOSGraphObject *obj)
 732{
 733    if (obj->start_hw) {
 734        obj->start_hw(obj);
 735    }
 736}
 737
 738char *qos_get_machine_type(char *name)
 739{
 740    while (*name != '\0' && *name != '/') {
 741        name++;
 742    }
 743
 744    if (!*name || !name[1]) {
 745        fprintf(stderr, "Machine name has to be of the form <arch>/<machine>\n");
 746        abort();
 747    }
 748
 749    return name + 1;
 750}
 751
 752void qos_delete_cmd_line(const char *name)
 753{
 754    QOSGraphNode *node = search_node(name);
 755    if (node) {
 756        g_free(node->command_line);
 757        node->command_line = NULL;
 758    }
 759}
 760