Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/68195/?format=api
{ "id": 68195, "url": "http://patches.dpdk.org/api/patches/68195/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20200411141428.1987768-6-jerinj@marvell.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<20200411141428.1987768-6-jerinj@marvell.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20200411141428.1987768-6-jerinj@marvell.com", "date": "2020-04-11T14:14:04", "name": "[v5,05/29] graph: implement internal graph operation helpers", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": true, "hash": "bf0c1a0ff2400ec55b836e9bfd99bc8824396512", "submitter": { "id": 1188, "url": "http://patches.dpdk.org/api/people/1188/?format=api", "name": "Jerin Jacob Kollanukkaran", "email": "jerinj@marvell.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/20200411141428.1987768-6-jerinj@marvell.com/mbox/", "series": [ { "id": 9314, "url": "http://patches.dpdk.org/api/series/9314/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=9314", "date": "2020-04-11T14:13:59", "name": "graph: introduce graph subsystem", "version": 5, "mbox": "http://patches.dpdk.org/series/9314/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/68195/comments/", "check": "warning", "checks": "http://patches.dpdk.org/api/patches/68195/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@inbox.dpdk.org", "Delivered-To": "patchwork@inbox.dpdk.org", "Received": [ "from dpdk.org (dpdk.org [92.243.14.124])\n\tby inbox.dpdk.org (Postfix) with ESMTP id C0777A059F;\n\tSat, 11 Apr 2020 16:15:25 +0200 (CEST)", "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 2D7A01C1E4;\n\tSat, 11 Apr 2020 16:14:48 +0200 (CEST)", "from mx0b-0016f401.pphosted.com (mx0b-0016f401.pphosted.com\n [67.231.156.173]) by dpdk.org (Postfix) with ESMTP id B633B1C1CD\n for <dev@dpdk.org>; Sat, 11 Apr 2020 16:14:46 +0200 (CEST)", "from pps.filterd (m0045851.ppops.net [127.0.0.1])\n by mx0b-0016f401.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id\n 03BEDDF6022391; Sat, 11 Apr 2020 07:14:45 -0700", "from sc-exch03.marvell.com ([199.233.58.183])\n by mx0b-0016f401.pphosted.com with ESMTP id 30bddkgar9-2\n (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT);\n Sat, 11 Apr 2020 07:14:44 -0700", "from DC5-EXCH01.marvell.com (10.69.176.38) by SC-EXCH03.marvell.com\n (10.93.176.83) with Microsoft SMTP Server (TLS) id 15.0.1497.2;\n Sat, 11 Apr 2020 07:14:43 -0700", "from maili.marvell.com (10.69.176.80) by DC5-EXCH01.marvell.com\n (10.69.176.38) with Microsoft SMTP Server id 15.0.1497.2 via Frontend\n Transport; Sat, 11 Apr 2020 07:14:43 -0700", "from jerin-lab.marvell.com (jerin-lab.marvell.com [10.28.34.14])\n by maili.marvell.com (Postfix) with ESMTP id 9C25F3F703F;\n Sat, 11 Apr 2020 07:14:38 -0700 (PDT)" ], "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com;\n h=from : to : cc :\n subject : date : message-id : in-reply-to : references : mime-version :\n content-transfer-encoding : content-type; s=pfpt0818;\n bh=3RS56uznIkbaCNzJ69U5Ez9YIIMlwBMOZQP7WQaBUS8=;\n b=fMkvRvesEFWup4ZDGP3L3dbZ5eGZClSwcUZukojKzRORbqOC+T3+VRU7o/1qHmTABCa9\n Ut2424LucFqmN4mzXUYEzPYkzXCBoOwS0NHy2+F0ntGWcT3S+lE6lv4i5m9B8HwzrLBH\n HIrvGavDN1LnLkBbx52h+j3HhcX0scj1dcGfmvxgJbKJumA12c+upR9RE/665UTzXykD\n scfXJ8BKupACRpk+KhXFdqhRDjmfESid2YVQG79xKDrA5dwYluY9syugosDdq7SXNGa9\n Sj7U9oyg6DAwHPSTIvDM3ez0e4Bli8ZCS9MFjLniJbZpk+wf0NvodYsiEU/Xb+YNjEaU CQ==", "From": "<jerinj@marvell.com>", "To": "Jerin Jacob <jerinj@marvell.com>, Kiran Kumar K <kirankumark@marvell.com>", "CC": "<dev@dpdk.org>, <thomas@monjalon.net>, <david.marchand@redhat.com>,\n <mdr@ashroe.eu>, <mattias.ronnblom@ericsson.com>,\n <pbhagavatula@marvell.com>, <ndabilpuram@marvell.com>,\n <xiao.w.wang@intel.com>, <amo@semihalf.com>", "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>\n <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\n definitions=2020-04-11_04:2020-04-09,\n 2020-04-11 signatures=0", "Subject": "[dpdk-dev] [PATCH v5 05/29] graph: implement internal graph\n\toperation helpers", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n <mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n <mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "From: Jerin Jacob <jerinj@marvell.com>\n\nAdding internal graph API helpers support to check whether a graph has\nisolated nodes and any node have a loop to itself and BFS\nalgorithm implementation etc.\n\nSigned-off-by: Jerin Jacob <jerinj@marvell.com>\nSigned-off-by: Nithin Dabilpuram <ndabilpuram@marvell.com>\n---\n lib/librte_graph/Makefile | 1 +\n lib/librte_graph/graph.c | 2 +-\n lib/librte_graph/graph_ops.c | 169 ++++++++++++++++++++++++++++++\n lib/librte_graph/graph_private.h | 173 +++++++++++++++++++++++++++++++\n lib/librte_graph/meson.build | 2 +-\n 5 files changed, 345 insertions(+), 2 deletions(-)\n create mode 100644 lib/librte_graph/graph_ops.c", "diff": "diff --git a/lib/librte_graph/Makefile b/lib/librte_graph/Makefile\nindex 2a6d86933..39ecb2652 100644\n--- a/lib/librte_graph/Makefile\n+++ b/lib/librte_graph/Makefile\n@@ -16,6 +16,7 @@ EXPORT_MAP := rte_graph_version.map\n # all source are stored in SRCS-y\n SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += node.c\n SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph.c\n+SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph_ops.c\n SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) += graph_debug.c\n \n # install header files\ndiff --git a/lib/librte_graph/graph.c b/lib/librte_graph/graph.c\nindex a9c124896..4c3f2fe7b 100644\n--- a/lib/librte_graph/graph.c\n+++ b/lib/librte_graph/graph.c\n@@ -7,7 +7,7 @@\n #include \"graph_private.h\"\n \n static rte_spinlock_t graph_lock = RTE_SPINLOCK_INITIALIZER;\n-\n+int rte_graph_logtype;\n void\n graph_spinlock_lock(void)\n {\ndiff --git a/lib/librte_graph/graph_ops.c b/lib/librte_graph/graph_ops.c\nnew file mode 100644\nindex 000000000..335595311\n--- /dev/null\n+++ b/lib/librte_graph/graph_ops.c\n@@ -0,0 +1,169 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(C) 2020 Marvell International Ltd.\n+ */\n+\n+#include <stdbool.h>\n+#include <string.h>\n+\n+#include <rte_common.h>\n+#include <rte_errno.h>\n+\n+#include \"graph_private.h\"\n+\n+/* Check whether a node has next_node to itself */\n+static inline int\n+node_has_loop_edge(struct node *node)\n+{\n+\trte_edge_t i;\n+\tchar *name;\n+\tint rc = 0;\n+\n+\tfor (i = 0; i < node->nb_edges; i++) {\n+\t\tif (strncmp(node->name, node->next_nodes[i],\n+\t\t\t RTE_NODE_NAMESIZE) == 0) {\n+\t\t\tname = node->name;\n+\t\t\trc = 1;\n+\t\t\tSET_ERR_JMP(EINVAL, fail, \"Node %s has loop to self\",\n+\t\t\t\t name);\n+\t\t}\n+\t}\n+fail:\n+\treturn rc;\n+}\n+\n+int\n+graph_node_has_loop_edge(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next)\n+\t\tif (node_has_loop_edge(graph_node->node))\n+\t\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n+rte_node_t\n+graph_src_nodes_count(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\trte_node_t rc = 0;\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next)\n+\t\tif (graph_node->node->flags & RTE_NODE_SOURCE_F)\n+\t\t\trc++;\n+\n+\tif (rc == 0)\n+\t\tSET_ERR_JMP(EINVAL, fail, \"Graph needs at least a source node\");\n+fail:\n+\treturn rc;\n+}\n+\n+/* Check whether a node has next_node to a source node */\n+int\n+graph_node_has_edge_to_src_node(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\tstruct node *node;\n+\trte_edge_t i;\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next) {\n+\t\tfor (i = 0; i < graph_node->node->nb_edges; i++) {\n+\t\t\tnode = graph_node->adjacency_list[i]->node;\n+\t\t\tif (node->flags & RTE_NODE_SOURCE_F)\n+\t\t\t\tSET_ERR_JMP(\n+\t\t\t\t\tEEXIST, fail,\n+\t\t\t\t\t\"Node %s points to the source node %s\",\n+\t\t\t\t\tgraph_node->node->name, node->name);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+fail:\n+\treturn 1;\n+}\n+\n+rte_node_t\n+graph_nodes_count(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\trte_node_t count = 0;\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next)\n+\t\tcount++;\n+\n+\treturn count;\n+}\n+\n+void\n+graph_mark_nodes_as_not_visited(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next)\n+\t\tgraph_node->visited = false;\n+}\n+\n+int\n+graph_bfs(struct graph *graph, struct graph_node *start)\n+{\n+\tstruct graph_node **queue, *v, *tmp;\n+\tuint16_t head = 0, tail = 0;\n+\trte_edge_t i;\n+\tsize_t sz;\n+\n+\tsz = sizeof(struct graph_node *) * graph_nodes_count(graph);\n+\tqueue = malloc(sz);\n+\tif (queue == NULL)\n+\t\tSET_ERR_JMP(ENOMEM, fail, \"Failed to alloc BFS queue of %zu\",\n+\t\t\t sz);\n+\n+\t/* BFS algorithm */\n+\tqueue[tail++] = start;\n+\tstart->visited = true;\n+\twhile (head != tail) {\n+\t\tv = queue[head++];\n+\t\tfor (i = 0; i < v->node->nb_edges; i++) {\n+\t\t\ttmp = v->adjacency_list[i];\n+\t\t\tif (tmp->visited == false) {\n+\t\t\t\tqueue[tail++] = tmp;\n+\t\t\t\ttmp->visited = true;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tfree(queue);\n+\treturn 0;\n+\n+fail:\n+\treturn -rte_errno;\n+}\n+\n+/* Check whether a node has connected path or parent node */\n+int\n+graph_has_isolated_node(struct graph *graph)\n+{\n+\tstruct graph_node *graph_node;\n+\n+\tgraph_mark_nodes_as_not_visited(graph);\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next) {\n+\t\tif (graph_node->node->flags & RTE_NODE_SOURCE_F) {\n+\t\t\tif (graph_node->node->nb_edges == 0)\n+\t\t\t\tSET_ERR_JMP(EINVAL, fail,\n+\t\t\t\t\t \"%s node needs minimum one edge\",\n+\t\t\t\t\t graph_node->node->name);\n+\t\t\tif (graph_bfs(graph, graph_node))\n+\t\t\t\tgoto fail;\n+\t\t}\n+\t}\n+\n+\tSTAILQ_FOREACH(graph_node, &graph->node_list, next)\n+\t\tif (graph_node->visited == false)\n+\t\t\tSET_ERR_JMP(EINVAL, fail, \"Found isolated node %s\",\n+\t\t\t\t graph_node->node->name);\n+\n+\treturn 0;\n+fail:\n+\treturn 1;\n+}\ndiff --git a/lib/librte_graph/graph_private.h b/lib/librte_graph/graph_private.h\nindex 6db04cee7..220a35e2a 100644\n--- a/lib/librte_graph/graph_private.h\n+++ b/lib/librte_graph/graph_private.h\n@@ -13,6 +13,16 @@\n \n #include \"rte_graph.h\"\n \n+extern int rte_graph_logtype;\n+\n+#define GRAPH_LOG(level, ...) \\\n+\trte_log(RTE_LOG_##level, rte_graph_logtype, \\\n+\t\tRTE_FMT(\"GRAPH: %s():%u \" RTE_FMT_HEAD(__VA_ARGS__, ) \"\\n\", \\\n+\t\t\t__func__, __LINE__, RTE_FMT_TAIL(__VA_ARGS__, )))\n+\n+#define graph_err(...) GRAPH_LOG(ERR, __VA_ARGS__)\n+#define graph_info(...) GRAPH_LOG(INFO, __VA_ARGS__)\n+#define graph_dbg(...) GRAPH_LOG(DEBUG, __VA_ARGS__)\n \n #define ID_CHECK(id, id_max) \\\n \tdo { \\\n@@ -22,6 +32,12 @@\n \t\t} \\\n \t} while (0)\n \n+#define SET_ERR_JMP(err, where, fmt, ...) \\\n+\tdo { \\\n+\t\tgraph_err(fmt, ##__VA_ARGS__); \\\n+\t\trte_errno = err; \\\n+\t\tgoto where; \\\n+\t} while (0)\n \n /**\n * @internal\n@@ -41,6 +57,52 @@ struct node {\n \tchar next_nodes[][RTE_NODE_NAMESIZE]; /**< Names of next nodes. */\n };\n \n+/**\n+ * @internal\n+ *\n+ * Structure that holds the graph node data.\n+ */\n+struct graph_node {\n+\tSTAILQ_ENTRY(graph_node) next; /**< Next graph node in the list. */\n+\tstruct node *node; /**< Pointer to internal node. */\n+\tbool visited; /**< Flag used in BFS to mark node visited. */\n+\tstruct graph_node *adjacency_list[]; /**< Adjacency list of the node. */\n+};\n+\n+/**\n+ * @internal\n+ *\n+ * Structure that holds graph internal data.\n+ */\n+struct graph {\n+\tSTAILQ_ENTRY(graph) next;\n+\t/**< List of graphs. */\n+\tchar name[RTE_GRAPH_NAMESIZE];\n+\t/**< Name of the graph. */\n+\tconst struct rte_memzone *mz;\n+\t/**< Memzone to store graph data. */\n+\trte_graph_off_t nodes_start;\n+\t/**< Node memory start offset in graph reel. */\n+\trte_node_t src_node_count;\n+\t/**< Number of source nodes in a graph. */\n+\tstruct rte_graph *graph;\n+\t/**< Pointer to graph data. */\n+\trte_node_t node_count;\n+\t/**< Total number of nodes. */\n+\tuint32_t cir_start;\n+\t/**< Circular buffer start offset in graph reel. */\n+\tuint32_t cir_mask;\n+\t/**< Circular buffer mask for wrap around. */\n+\trte_graph_t id;\n+\t/**< Graph identifier. */\n+\tsize_t mem_sz;\n+\t/**< Memory size of the graph. */\n+\tint socket;\n+\t/**< Socket identifier where memory is allocated. */\n+\tSTAILQ_HEAD(gnode_list, graph_node) node_list;\n+\t/**< Nodes in a graph. */\n+};\n+\n /* Node functions */\n STAILQ_HEAD(node_head, node);\n \n@@ -67,6 +129,19 @@ struct node_head *node_list_head_get(void);\n */\n struct node *node_from_name(const char *name);\n \n+/* Graph list functions */\n+STAILQ_HEAD(graph_head, graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Get the head of the graph list.\n+ *\n+ * @return\n+ * Pointer to the graph head.\n+ */\n+struct graph_head *graph_list_head_get(void);\n+\n /* Lock functions */\n /**\n * @internal\n@@ -82,6 +157,104 @@ void graph_spinlock_lock(void);\n */\n void graph_spinlock_unlock(void);\n \n+/* Graph operations */\n+/**\n+ * @internal\n+ *\n+ * Run a BFS(Breadth First Search) on the graph marking all\n+ * the graph nodes as visited.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ * @param start\n+ * Pointer to the starting graph node.\n+ *\n+ * @return\n+ * - 0: Success.\n+ * - -ENOMEM: Not enough memory for BFS.\n+ */\n+int graph_bfs(struct graph *graph, struct graph_node *start);\n+\n+/**\n+ * @internal\n+ *\n+ * Check if there is an isolated node in the given graph.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ *\n+ * @return\n+ * - 0: No isolated node found.\n+ * - 1: Isolated node found.\n+ */\n+int graph_has_isolated_node(struct graph *graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Check whether a node in the graph has next_node to a source node.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ *\n+ * @return\n+ * - 0: Node has an edge to source node.\n+ * - 1: Node doesn't have an edge to source node.\n+ */\n+int graph_node_has_edge_to_src_node(struct graph *graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Checks whether node in the graph has a edge to itself i.e. forms a\n+ * loop.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ *\n+ * @return\n+ * - 0: Node has an edge to itself.\n+ * - 1: Node doesn't have an edge to itself.\n+ */\n+int graph_node_has_loop_edge(struct graph *graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Get the count of source nodes in the graph.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ *\n+ * @return\n+ * Number of source nodes.\n+ */\n+rte_node_t graph_src_nodes_count(struct graph *graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Get the count of total number of nodes in the graph.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ *\n+ * @return\n+ * Number of nodes.\n+ */\n+rte_node_t graph_nodes_count(struct graph *graph);\n+\n+/**\n+ * @internal\n+ *\n+ * Clear the visited flag of all the nodes in the graph.\n+ *\n+ * @param graph\n+ * Pointer to the internal graph object.\n+ */\n+void graph_mark_nodes_as_not_visited(struct graph *graph);\n+\n+\n /**\n * @internal\n *\ndiff --git a/lib/librte_graph/meson.build b/lib/librte_graph/meson.build\nindex 01512182f..16e0625c1 100644\n--- a/lib/librte_graph/meson.build\n+++ b/lib/librte_graph/meson.build\n@@ -4,7 +4,7 @@\n \n name = 'graph'\n \n-sources = files('node.c', 'graph.c', 'graph_debug.c')\n+sources = files('node.c', 'graph.c', 'graph_ops.c', 'graph_debug.c')\n headers = files('rte_graph.h')\n allow_experimental_apis = true\n \n", "prefixes": [ "v5", "05/29" ] }