[dpdk-dev] [PATCH v3 05/29] graph: implement internal graph operation helpers

[Wang, Xiao W]

Hi,

Comment inline.

Best Regards,
Xiao

> -----Original Message-----
> From: dev <dev-bounces at dpdk.org> On Behalf Of jerinj at marvell.com
> Sent: Wednesday, April 1, 2020 3:29 AM
> To: Jerin Jacob <jerinj at marvell.com>; Kiran Kumar K
> <kirankumark at marvell.com>
> Cc: dev at dpdk.org; thomas at monjalon.net; david.marchand at redhat.com;
> mdr at ashroe.eu; mattias.ronnblom at ericsson.com;
> pbhagavatula at marvell.com; ndabilpuram at marvell.com
> Subject: [dpdk-dev] [PATCH v3 05/29] graph: implement internal graph
> operation helpers
> 
> From: Jerin Jacob <jerinj at 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 <jerinj at marvell.com>
> Signed-off-by: Nithin Dabilpuram <ndabilpuram at 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?