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 1C53EA0577; Mon, 6 Apr 2020 15:47:40 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 74AD22B86; Mon, 6 Apr 2020 15:47:39 +0200 (CEST) Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by dpdk.org (Postfix) with ESMTP id 89DB0F12 for ; Mon, 6 Apr 2020 15:47:37 +0200 (CEST) IronPort-SDR: R27wn9H/shHIpjl29a4FZKtzWg2GbpZHpItYZj34KRm3ZzORWbi4bbEmscqwyAV3uJ/3wIyE/n /S3qqMy2anTw== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga007.fm.intel.com ([10.253.24.52]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 06 Apr 2020 06:47:36 -0700 IronPort-SDR: 1V+ZpqYGW7L8M64BOuXkLxrsHvNXCUIuPzTLtPo/bkP7LLkUwhR5cHZtXQcTNK15Myns5W457z ADM3bUQBJunw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,351,1580803200"; d="scan'208";a="241785977" Received: from fmsmsx106.amr.corp.intel.com ([10.18.124.204]) by fmsmga007.fm.intel.com with ESMTP; 06 Apr 2020 06:47:36 -0700 Received: from fmsmsx111.amr.corp.intel.com (10.18.116.5) by FMSMSX106.amr.corp.intel.com (10.18.124.204) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 6 Apr 2020 06:47:36 -0700 Received: from FMSEDG001.ED.cps.intel.com (10.1.192.133) by fmsmsx111.amr.corp.intel.com (10.18.116.5) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 6 Apr 2020 06:47:35 -0700 Received: from NAM11-CO1-obe.outbound.protection.outlook.com (104.47.56.175) by edgegateway.intel.com (192.55.55.68) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 6 Apr 2020 06:47:35 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=SJfJkrRrFOlXNzMBj2YdiKBLAqsxNZxYVlmHeq53Hgtg2Yxm8C3UR9tRz9ac/vmedmnofj2UbKyqfyRzJewvxUmbwe6/x91Y/TSMdPpY9HeJwRrWF3hWtwKPDWBa9pih1JzVdfPv0yfgPI+3I26Kdzr36vCZt+46k4i6zr4uXqa3L7h300ES2D+2YLcJnBJX6b5rIAqCdh/ntAamJOt2m3h13o/cObLZ00WHCnx+UQZOWJ0v+0gSwMIjlmK2cLkSkCRNb/qpSPRr4L6A+slzYedrGVX9koy0ZpA0631Y9itnYJxSyoxGCp0kznlyFF3EcApLhrUonQ4nidMLdaQj7Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=jAeE7PYgRKaHdOJr0NmVEGCWpMvvufMrgpHMtw68Z+0=; b=XybIC9MA32dp/A5AESi/o0FQrlsk8x6WEqt+ekMCzN7yNQJhHap9jaEpC+yvEugaE2g0nGqFHhPH8nBDa6LboYjlwYCiMP7GWa9MfvXvdewHT+Ug4m29B92mOsB9+jUrFNQB2YHudrarPlU0b3KRYyJceoAEcc8g8RQR1pBs9b/3fZWRjY/9WsgXN3K1tkmV8VZ95mmwwP3IvO3ZMybmNHxwJ4QKfERQJEvSzX3WasUx6k2FRRZJa0TZn0H0oLIpWGnLTh03s2rpUuneZSMV3Fd+Dqbyvm+5z75uvIcfUdpjZPhMQccqlGhhXCj6gjAIsXVATi1ETY0N8XxC30/lAw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com; s=selector2-intel-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=jAeE7PYgRKaHdOJr0NmVEGCWpMvvufMrgpHMtw68Z+0=; b=MwSXlS53pqSK9DIKhV59O26mIw6XFNrV83y2vWVYTy8TdIRjC9taFviq3KPRlhX1+K+cLbQjLBUicjoB1L90kbNpRAnoMaU4nU45ilraihri1HWe+4PDVnJKffMLXYHFDSQGfyBjNmUn3mRmYr73G2a3n9dSHsceLAicLl+LgYg= Received: from BN6PR11MB1473.namprd11.prod.outlook.com (2603:10b6:405:a::16) by BN6PR11MB3892.namprd11.prod.outlook.com (2603:10b6:405:80::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2878.19; Mon, 6 Apr 2020 13:47:34 +0000 Received: from BN6PR11MB1473.namprd11.prod.outlook.com ([fe80::d013:5d99:e57e:570e]) by BN6PR11MB1473.namprd11.prod.outlook.com ([fe80::d013:5d99:e57e:570e%7]) with mapi id 15.20.2878.018; Mon, 6 Apr 2020 13:47:34 +0000 From: "Wang, Xiao W" To: "jerinj@marvell.com" , Kiran Kumar K CC: "dev@dpdk.org" , "thomas@monjalon.net" , "david.marchand@redhat.com" , "mdr@ashroe.eu" , "mattias.ronnblom@ericsson.com" , "pbhagavatula@marvell.com" , "ndabilpuram@marvell.com" Thread-Topic: [dpdk-dev] [PATCH v3 05/29] graph: implement internal graph operation helpers Thread-Index: AQHWB5L8Fm6Jtq9agEmnEwq7mHVEaqhsIduw Date: Mon, 6 Apr 2020 13:47:33 +0000 Message-ID: References: <20200326165644.866053-1-jerinj@marvell.com> <20200331192945.2466880-1-jerinj@marvell.com> <20200331192945.2466880-6-jerinj@marvell.com> In-Reply-To: <20200331192945.2466880-6-jerinj@marvell.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=xiao.w.wang@intel.com; x-originating-ip: [192.55.52.195] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: f7452245-a3b0-47b5-6c8e-08d7da310f5d x-ms-traffictypediagnostic: BN6PR11MB3892: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:154; x-forefront-prvs: 0365C0E14B x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BN6PR11MB1473.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(10019020)(39860400002)(396003)(346002)(376002)(136003)(366004)(66556008)(64756008)(5660300002)(66446008)(2906002)(55016002)(66946007)(76116006)(86362001)(478600001)(66476007)(4326008)(54906003)(26005)(316002)(33656002)(110136005)(6506007)(9686003)(71200400001)(81156014)(81166006)(52536014)(8936002)(186003)(7696005)(53546011); DIR:OUT; SFP:1102; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: l/tG6BrcvOg2WCMkcFNpMIUPGwUtgTvTYy59IUUywYUqrasKygxRC6P0e5D2MrF4DO2ykjf4CdA1x+6yNrbZi0Jl+KZ91WJBKnxvWTO1/2G7ATeL2n59GJqrEar2Hm85I2bFTf4elLy/VTgt5G8aFenktlqkk2ci240Gt187GkJDI7+N6yLWKJz5eofR8+9OUcTDCb2PGlG1jUxJPkxKc0m8xbezyubvzz66yJOs3cF5F9LKb1GqSfAHnZKuggCWJAoEBVeYF2GS7qkNxGJB71GL71UraoWnL9ku5uxXRvJ0xDD60n85cObFqJH84S3P2P2tNxv/WOCMOz5piZiX0NbIYPZafyjJ9lhFNglSWQ2Bd0wfB9ljTy+G/IEQJar57LJ6NMGK0PloLDKaI0vk6NkfpuDAlmRO/49u0CEDs9IqUTOjXLYEgDsXVwB0oRHn x-ms-exchange-antispam-messagedata: D+9UT1ohdc9pMrsjoVmJ6zRqKzHAkSlC2/4j6tKJB48ItL1mXzexbuqN/jT6cmw63MPjtG0rXmghNp5j6fmWmaC/jPPTMIGNJu4Ykh2tPukA+XGHCgRQwvCRRKl4MApaY0MWnqFrRhTpYVn3f0VELw== x-ms-exchange-transport-forked: True Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: f7452245-a3b0-47b5-6c8e-08d7da310f5d X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Apr 2020 13:47:34.0169 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: pkA42yrvzEuY3jJ0SoEX9LtAO/q3/SxU/ENcmMqvaSX8HdABMkcPUY7pAX/7N9dtpNx3+5TsLKy4pzanKg5ZvQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN6PR11MB3892 X-OriginatorOrg: intel.com Subject: Re: [dpdk-dev] [PATCH v3 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" Hi, Comment inline. Best Regards, Xiao > -----Original Message----- > From: dev On Behalf Of jerinj@marvell.com > Sent: Wednesday, April 1, 2020 3:29 AM > To: Jerin Jacob ; Kiran Kumar K > > Cc: dev@dpdk.org; thomas@monjalon.net; david.marchand@redhat.com; > mdr@ashroe.eu; mattias.ronnblom@ericsson.com; > pbhagavatula@marvell.com; ndabilpuram@marvell.com > Subject: [dpdk-dev] [PATCH v3 05/29] graph: implement internal graph > operation helpers >=20 > From: Jerin Jacob >=20 > 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. >=20 > 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 >=20 > 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 :=3D rte_graph_version.map > # all source are stored in SRCS-y > SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) +=3D node.c > SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) +=3D graph.c > +SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) +=3D graph_ops.c > SRCS-$(CONFIG_RTE_LIBRTE_GRAPH) +=3D graph_debug.c >=20 > # 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" >=20 > static rte_spinlock_t graph_lock =3D 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 =3D 0; > + > + for (i =3D 0; i < node->nb_edges; i++) { > + if (strncmp(node->name, node->next_nodes[i], > + RTE_NODE_NAMESIZE) =3D=3D 0) { > + name =3D node->name; > + rc =3D 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 =3D 0; > + > + STAILQ_FOREACH(graph_node, &graph->node_list, next) > + if (graph_node->node->flags & RTE_NODE_SOURCE_F) > + rc++; > + > + if (rc =3D=3D 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 =3D 0; i < graph_node->node->nb_edges; i++) { > + node =3D 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 =3D 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 =3D false; > +} > + > +int > +graph_bfs(struct graph *graph, struct graph_node *start) > +{ > + struct graph_node **queue, *v, *tmp; > + uint16_t head =3D 0, tail =3D 0; > + rte_edge_t i; > + size_t sz; > + > + sz =3D sizeof(struct graph_node *) * graph_nodes_count(graph); > + queue =3D malloc(sz); > + if (queue =3D=3D NULL) > + SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue > of %zu", > + sz); > + > + /* BFS algorithm */ > + queue[tail++] =3D start; > + start->visited =3D true; > + while (head !=3D tail) { > + v =3D queue[head++]; > + for (i =3D 0; i < v->node->nb_edges; i++) { > + tmp =3D v->adjacency_list[i]; > + if (tmp->visited =3D=3D false) { > + queue[tail++] =3D tmp; > + tmp->visited =3D 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 =3D=3D 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 =3D=3D 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?