From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id C0777A059F; Sat, 11 Apr 2020 16:15:25 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 2D7A01C1E4; Sat, 11 Apr 2020 16:14:48 +0200 (CEST) Received: from mx0b-0016f401.pphosted.com (mx0b-0016f401.pphosted.com [67.231.156.173]) by dpdk.org (Postfix) with ESMTP id B633B1C1CD for ; Sat, 11 Apr 2020 16:14:46 +0200 (CEST) Received: from pps.filterd (m0045851.ppops.net [127.0.0.1]) by mx0b-0016f401.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 03BEDDF6022391; Sat, 11 Apr 2020 07:14:45 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=pfpt0818; bh=3RS56uznIkbaCNzJ69U5Ez9YIIMlwBMOZQP7WQaBUS8=; b=fMkvRvesEFWup4ZDGP3L3dbZ5eGZClSwcUZukojKzRORbqOC+T3+VRU7o/1qHmTABCa9 Ut2424LucFqmN4mzXUYEzPYkzXCBoOwS0NHy2+F0ntGWcT3S+lE6lv4i5m9B8HwzrLBH HIrvGavDN1LnLkBbx52h+j3HhcX0scj1dcGfmvxgJbKJumA12c+upR9RE/665UTzXykD scfXJ8BKupACRpk+KhXFdqhRDjmfESid2YVQG79xKDrA5dwYluY9syugosDdq7SXNGa9 Sj7U9oyg6DAwHPSTIvDM3ez0e4Bli8ZCS9MFjLniJbZpk+wf0NvodYsiEU/Xb+YNjEaU CQ== Received: from sc-exch03.marvell.com ([199.233.58.183]) by mx0b-0016f401.pphosted.com with ESMTP id 30bddkgar9-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Sat, 11 Apr 2020 07:14:44 -0700 Received: from DC5-EXCH01.marvell.com (10.69.176.38) by SC-EXCH03.marvell.com (10.93.176.83) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Sat, 11 Apr 2020 07:14:43 -0700 Received: from maili.marvell.com (10.69.176.80) by DC5-EXCH01.marvell.com (10.69.176.38) with Microsoft SMTP Server id 15.0.1497.2 via Frontend Transport; Sat, 11 Apr 2020 07:14:43 -0700 Received: from jerin-lab.marvell.com (jerin-lab.marvell.com [10.28.34.14]) by maili.marvell.com (Postfix) with ESMTP id 9C25F3F703F; Sat, 11 Apr 2020 07:14:38 -0700 (PDT) From: To: Jerin Jacob , Kiran Kumar K CC: , , , , , , , , Date: Sat, 11 Apr 2020 19:44:04 +0530 Message-ID: <20200411141428.1987768-6-jerinj@marvell.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20200411141428.1987768-1-jerinj@marvell.com> References: <20200405085613.1336841-1-jerinj@marvell.com> <20200411141428.1987768-1-jerinj@marvell.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.138, 18.0.676 definitions=2020-04-11_04:2020-04-09, 2020-04-11 signatures=0 Subject: [dpdk-dev] [PATCH v5 05/29] graph: implement internal graph operation helpers X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" From: Jerin Jacob 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 | 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 +#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 6db04cee7..220a35e2a 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 01512182f..16e0625c1 100644 --- a/lib/librte_graph/meson.build +++ b/lib/librte_graph/meson.build @@ -4,7 +4,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') allow_experimental_apis = true -- 2.25.1