Hi,
Comment inline.
Best Regards,
Xiao
> -----Original Message-----
> From: dev <dev-boun...@dpdk.org> On Behalf Of jer...@marvell.com
> Sent: Wednesday, April 1, 2020 3:29 AM
> To: Jerin Jacob <jer...@marvell.com>; Kiran Kumar K
> <kirankum...@marvell.com>
> Cc: dev@dpdk.org; tho...@monjalon.net; david.march...@redhat.com;
> m...@ashroe.eu; mattias.ronnb...@ericsson.com;
> pbhagavat...@marvell.com; ndabilpu...@marvell.com
> Subject: [dpdk-dev] [PATCH v3 05/29] graph: implement internal graph
> operation helpers
>
> From: Jerin Jacob <jer...@marvell.com>
>
> 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 <jer...@marvell.com>
> Signed-off-by: Nithin Dabilpuram <ndabilpu...@marvell.com>
> ---
> lib/librte_graph/Makefile | 1 +
> lib/librte_graph/graph.c | 2 +-
> 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(+), 2 deletions(-)
> create mode 100644 lib/librte_graph/graph_ops.c
>
> diff --git a/lib/librte_graph/Makefile b/lib/librte_graph/Makefile
> index 2a6d86933..39ecb2652 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 a9c124896..4c3f2fe7b 100644
> --- a/lib/librte_graph/graph.c
> +++ b/lib/librte_graph/graph.c
> @@ -7,7 +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 000000000..335595311
> --- /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 <stdbool.h>
> +#include <string.h>
> +
> +#include <rte_common.h>
> +#include <rte_errno.h>
> +
> +#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;
> +}
Do you think we even need to detect loop which is neither self-looping nor
looping-to-src,
or in another word, loop constructed by some intermediate nodes?
