/*
* 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.1 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 "qgraph_internal.h"
#include "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);
QOSGraphEdgeOptions def_opts = { };
if (!list) {
list = g_new0(QOSGraphEdgeList, 1);
key = g_strdup(source);
g_hash_table_insert(edge_table, key, list);
}
if (!opts) {
opts = &def_opts;
}
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_memdup2(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->qemu_name);
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)
{
const char *name = node->qemu_name ?: node->name;
node->command_line = g_strconcat(" -device ", 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);
QOSGraphTestOptions def_opts = { };
if (!opts) {
opts = &def_opts;
}
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_create_driver_named(const char *name, const char *qemu_name,
QOSCreateDriverFunc function)
{
QOSGraphNode *node = create_node(name, QNODE_DRIVER);
node->qemu_name = g_strdup(qemu_name);
build_driver_cmd_line(node);
node->u.driver.constructor = function;
}
void qos_node_contains(const char *container, const char *contained,
QOSGraphEdgeOptions *opts, ...)
{
va_list va;
if (opts == NULL) {
add_edge(container, contained, QEDGE_CONTAINS, NULL);
return;
}
va_start(va, opts);
do {
add_edge(container, contained, QEDGE_CONTAINS, opts);
opts = va_arg(va, QOSGraphEdgeOptions *);
} 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);
}
static void qos_graph_node_set_availability_explicit(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_explicit(e->dest, av);
}
}
}
/*
* Behaves as qos_graph_node_set_availability_explicit(), except that the
* former always matches by node name only, whereas this function matches both
* by node name and node's optional 'qemu_name' field.
*/
void qos_graph_node_set_availability(const char *node, bool av)
{
GList *l;
QOSGraphEdgeList *elist;
QOSGraphEdge *e, *next;
QOSGraphNode *n;
GList *keys = g_hash_table_get_keys(node_table);
for (l = keys; l != NULL; l = l->next) {
const gchar *key = l->data;
n = g_hash_table_lookup(node_table, key);
/*
* node's 'qemu_name' is set if there is more than one device with
* the same QEMU (QMP) device name
*/
const char *node_name = n->qemu_name ?: n->name;
if (g_strcmp0(node_name, node) == 0) {
n->available = av;
elist = get_edgelist(n->name);
if (elist) {
QSLIST_FOREACH_SAFE(e, elist, edge_list, next) {
if (e->type == QEDGE_CONTAINS || e->type == QEDGE_PRODUCES)
{
qos_graph_node_set_availability_explicit(e->dest, av);
}
}
}
}
}
g_list_free(keys);
}
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;
}
}
void qos_dump_graph(void)
{
GList *keys;
GList *l;
QOSGraphEdgeList *list;
QOSGraphEdge *e, *next;
QOSGraphNode *dest_node, *node;
qos_printf("ALL QGRAPH EDGES: {\n");
keys = g_hash_table_get_keys(edge_table);
for (l = keys; l != NULL; l = l->next) {
const gchar *key = l->data;
qos_printf("\t src='%s'\n", key);
list = get_edgelist(key);
QSLIST_FOREACH_SAFE(e, list, edge_list, next) {
dest_node = g_hash_table_lookup(node_table, e->dest);
qos_printf("\t\t|-> dest='%s' type=%d (node=%p)",
e->dest, e->type, dest_node);
if (!dest_node) {
qos_printf_literal(" <------- ERROR !");
}
qos_printf_literal("\n");
}
}
g_list_free(keys);
qos_printf("}\n");
qos_printf("ALL QGRAPH NODES: {\n");
keys = g_hash_table_get_keys(node_table);
for (l = keys; l != NULL; l = l->next) {
const gchar *key = l->data;
node = g_hash_table_lookup(node_table, key);
qos_printf("\t name='%s' ", key);
if (node->qemu_name) {
qos_printf_literal("qemu_name='%s' ", node->qemu_name);
}
qos_printf_literal("type=%d cmd_line='%s' [%s]\n",
node->type, node->command_line,
node->available ? "available" : "UNAVAILABLE"
);
}
g_list_free(keys);
qos_printf("}\n");
}
