From 32bd4751f941be8f77b3a260f947f21a7115964d Mon Sep 17 00:00:00 2001 From: Jerin Jacob Date: Sat, 11 Apr 2020 19:44:04 +0530 Subject: [PATCH] graph: implement internal operation helpers Adding internal graph API helpers support to check whether a graph has isolated nodes and any node have a loop to itself and BFS algorithm implementation etc. Signed-off-by: Jerin Jacob Signed-off-by: Nithin Dabilpuram --- lib/librte_graph/Makefile | 1 + lib/librte_graph/graph.c | 1 + lib/librte_graph/graph_ops.c | 169 ++++++++++++++++++++++++++++++ lib/librte_graph/graph_private.h | 173 +++++++++++++++++++++++++++++++ lib/librte_graph/meson.build | 2 +- 5 files changed, 345 insertions(+), 1 deletion(-) create mode 100644 lib/librte_graph/graph_ops.c diff --git a/lib/librte_graph/Makefile b/lib/librte_graph/Makefile index 17e087deaf..9cb8066e75 100644 --- a/lib/librte_graph/Makefile +++ b/lib/librte_graph/Makefile @@ -16,6 +16,7 @@ EXPORT_MAP := rte_graph_version.map # all source are stored in SRCS-y SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += node.c SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph.c +SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph_ops.c SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph_debug.c # install header files diff --git a/lib/librte_graph/graph.c b/lib/librte_graph/graph.c index a9c124896a..21c32cfeda 100644 --- a/lib/librte_graph/graph.c +++ b/lib/librte_graph/graph.c @@ -7,6 +7,7 @@ #include "graph_private.h" static rte_spinlock_t graph_lock = RTE_SPINLOCK_INITIALIZER; +int rte_graph_logtype; void graph_spinlock_lock(void) diff --git a/lib/librte_graph/graph_ops.c b/lib/librte_graph/graph_ops.c new file mode 100644 index 0000000000..3355953118 --- /dev/null +++ b/lib/librte_graph/graph_ops.c @@ -0,0 +1,169 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(C) 2020 Marvell International Ltd. + */ + +#include +#include + +#include +#include + +#include "graph_private.h" + +/* Check whether a node has next_node to itself */ +static inline int +node_has_loop_edge(struct node *node) +{ + rte_edge_t i; + char *name; + int rc = 0; + + for (i = 0; i < node->nb_edges; i++) { + if (strncmp(node->name, node->next_nodes[i], + RTE_NODE_NAMESIZE) == 0) { + name = node->name; + rc = 1; + SET_ERR_JMP(EINVAL, fail, "Node %s has loop to self", + name); + } + } +fail: + return rc; +} + +int +graph_node_has_loop_edge(struct graph *graph) +{ + struct graph_node *graph_node; + + STAILQ_FOREACH(graph_node, &graph->node_list, next) + if (node_has_loop_edge(graph_node->node)) + return 1; + + return 0; +} + +rte_node_t +graph_src_nodes_count(struct graph *graph) +{ + struct graph_node *graph_node; + rte_node_t rc = 0; + + STAILQ_FOREACH(graph_node, &graph->node_list, next) + if (graph_node->node->flags & RTE_NODE_SOURCE_F) + rc++; + + if (rc == 0) + SET_ERR_JMP(EINVAL, fail, "Graph needs at least a source node"); +fail: + return rc; +} + +/* Check whether a node has next_node to a source node */ +int +graph_node_has_edge_to_src_node(struct graph *graph) +{ + struct graph_node *graph_node; + struct node *node; + rte_edge_t i; + + STAILQ_FOREACH(graph_node, &graph->node_list, next) { + for (i = 0; i < graph_node->node->nb_edges; i++) { + node = graph_node->adjacency_list[i]->node; + if (node->flags & RTE_NODE_SOURCE_F) + SET_ERR_JMP( + EEXIST, fail, + "Node %s points to the source node %s", + graph_node->node->name, node->name); + } + } + + return 0; +fail: + return 1; +} + +rte_node_t +graph_nodes_count(struct graph *graph) +{ + struct graph_node *graph_node; + rte_node_t count = 0; + + STAILQ_FOREACH(graph_node, &graph->node_list, next) + count++; + + return count; +} + +void +graph_mark_nodes_as_not_visited(struct graph *graph) +{ + struct graph_node *graph_node; + + STAILQ_FOREACH(graph_node, &graph->node_list, next) + graph_node->visited = false; +} + +int +graph_bfs(struct graph *graph, struct graph_node *start) +{ + struct graph_node **queue, *v, *tmp; + uint16_t head = 0, tail = 0; + rte_edge_t i; + size_t sz; + + sz = sizeof(struct graph_node *) * graph_nodes_count(graph); + queue = malloc(sz); + if (queue == NULL) + SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu", + sz); + + /* BFS algorithm */ + queue[tail++] = start; + start->visited = true; + while (head != tail) { + v = queue[head++]; + for (i = 0; i < v->node->nb_edges; i++) { + tmp = v->adjacency_list[i]; + if (tmp->visited == false) { + queue[tail++] = tmp; + tmp->visited = true; + } + } + } + + free(queue); + return 0; + +fail: + return -rte_errno; +} + +/* Check whether a node has connected path or parent node */ +int +graph_has_isolated_node(struct graph *graph) +{ + struct graph_node *graph_node; + + graph_mark_nodes_as_not_visited(graph); + + STAILQ_FOREACH(graph_node, &graph->node_list, next) { + if (graph_node->node->flags & RTE_NODE_SOURCE_F) { + if (graph_node->node->nb_edges == 0) + SET_ERR_JMP(EINVAL, fail, + "%s node needs minimum one edge", + graph_node->node->name); + if (graph_bfs(graph, graph_node)) + goto fail; + } + } + + STAILQ_FOREACH(graph_node, &graph->node_list, next) + if (graph_node->visited == false) + SET_ERR_JMP(EINVAL, fail, "Found isolated node %s", + graph_node->node->name); + + return 0; +fail: + return 1; +} diff --git a/lib/librte_graph/graph_private.h b/lib/librte_graph/graph_private.h index 6db04cee73..220a35e2a9 100644 --- a/lib/librte_graph/graph_private.h +++ b/lib/librte_graph/graph_private.h @@ -13,6 +13,16 @@ #include "rte_graph.h" +extern int rte_graph_logtype; + +#define GRAPH_LOG(level, ...) \ + rte_log(RTE_LOG_##level, rte_graph_logtype, \ + RTE_FMT("GRAPH: %s():%u " RTE_FMT_HEAD(__VA_ARGS__, ) "\n", \ + __func__, __LINE__, RTE_FMT_TAIL(__VA_ARGS__, ))) + +#define graph_err(...) GRAPH_LOG(ERR, __VA_ARGS__) +#define graph_info(...) GRAPH_LOG(INFO, __VA_ARGS__) +#define graph_dbg(...) GRAPH_LOG(DEBUG, __VA_ARGS__) #define ID_CHECK(id, id_max) \ do { \ @@ -22,6 +32,12 @@ } \ } while (0) +#define SET_ERR_JMP(err, where, fmt, ...) \ + do { \ + graph_err(fmt, ##__VA_ARGS__); \ + rte_errno = err; \ + goto where; \ + } while (0) /** * @internal @@ -41,6 +57,52 @@ struct node { char next_nodes[][RTE_NODE_NAMESIZE]; /**< Names of next nodes. */ }; +/** + * @internal + * + * Structure that holds the graph node data. + */ +struct graph_node { + STAILQ_ENTRY(graph_node) next; /**< Next graph node in the list. */ + struct node *node; /**< Pointer to internal node. */ + bool visited; /**< Flag used in BFS to mark node visited. */ + struct graph_node *adjacency_list[]; /**< Adjacency list of the node. */ +}; + +/** + * @internal + * + * Structure that holds graph internal data. + */ +struct graph { + STAILQ_ENTRY(graph) next; + /**< List of graphs. */ + char name[RTE_GRAPH_NAMESIZE]; + /**< Name of the graph. */ + const struct rte_memzone *mz; + /**< Memzone to store graph data. */ + rte_graph_off_t nodes_start; + /**< Node memory start offset in graph reel. */ + rte_node_t src_node_count; + /**< Number of source nodes in a graph. */ + struct rte_graph *graph; + /**< Pointer to graph data. */ + rte_node_t node_count; + /**< Total number of nodes. */ + uint32_t cir_start; + /**< Circular buffer start offset in graph reel. */ + uint32_t cir_mask; + /**< Circular buffer mask for wrap around. */ + rte_graph_t id; + /**< Graph identifier. */ + size_t mem_sz; + /**< Memory size of the graph. */ + int socket; + /**< Socket identifier where memory is allocated. */ + STAILQ_HEAD(gnode_list, graph_node) node_list; + /**< Nodes in a graph. */ +}; + /* Node functions */ STAILQ_HEAD(node_head, node); @@ -67,6 +129,19 @@ struct node_head *node_list_head_get(void); */ struct node *node_from_name(const char *name); +/* Graph list functions */ +STAILQ_HEAD(graph_head, graph); + +/** + * @internal + * + * Get the head of the graph list. + * + * @return + * Pointer to the graph head. + */ +struct graph_head *graph_list_head_get(void); + /* Lock functions */ /** * @internal @@ -82,6 +157,104 @@ void graph_spinlock_lock(void); */ void graph_spinlock_unlock(void); +/* Graph operations */ +/** + * @internal + * + * Run a BFS(Breadth First Search) on the graph marking all + * the graph nodes as visited. + * + * @param graph + * Pointer to the internal graph object. + * @param start + * Pointer to the starting graph node. + * + * @return + * - 0: Success. + * - -ENOMEM: Not enough memory for BFS. + */ +int graph_bfs(struct graph *graph, struct graph_node *start); + +/** + * @internal + * + * Check if there is an isolated node in the given graph. + * + * @param graph + * Pointer to the internal graph object. + * + * @return + * - 0: No isolated node found. + * - 1: Isolated node found. + */ +int graph_has_isolated_node(struct graph *graph); + +/** + * @internal + * + * Check whether a node in the graph has next_node to a source node. + * + * @param graph + * Pointer to the internal graph object. + * + * @return + * - 0: Node has an edge to source node. + * - 1: Node doesn't have an edge to source node. + */ +int graph_node_has_edge_to_src_node(struct graph *graph); + +/** + * @internal + * + * Checks whether node in the graph has a edge to itself i.e. forms a + * loop. + * + * @param graph + * Pointer to the internal graph object. + * + * @return + * - 0: Node has an edge to itself. + * - 1: Node doesn't have an edge to itself. + */ +int graph_node_has_loop_edge(struct graph *graph); + +/** + * @internal + * + * Get the count of source nodes in the graph. + * + * @param graph + * Pointer to the internal graph object. + * + * @return + * Number of source nodes. + */ +rte_node_t graph_src_nodes_count(struct graph *graph); + +/** + * @internal + * + * Get the count of total number of nodes in the graph. + * + * @param graph + * Pointer to the internal graph object. + * + * @return + * Number of nodes. + */ +rte_node_t graph_nodes_count(struct graph *graph); + +/** + * @internal + * + * Clear the visited flag of all the nodes in the graph. + * + * @param graph + * Pointer to the internal graph object. + */ +void graph_mark_nodes_as_not_visited(struct graph *graph); + + /** * @internal * diff --git a/lib/librte_graph/meson.build b/lib/librte_graph/meson.build index 66daac64d7..af2695d86c 100644 --- a/lib/librte_graph/meson.build +++ b/lib/librte_graph/meson.build @@ -3,7 +3,7 @@ name = 'graph' -sources = files('node.c', 'graph.c', 'graph_debug.c') +sources = files('node.c', 'graph.c', 'graph_ops.c', 'graph_debug.c') headers = files('rte_graph.h') deps += ['eal'] -- 2.20.1