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 24FB0A0588; Tue, 7 Apr 2020 14:16:43 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 6B4C22BE2; Tue, 7 Apr 2020 14:16:42 +0200 (CEST) Received: from mail-lf1-f67.google.com (mail-lf1-f67.google.com [209.85.167.67]) by dpdk.org (Postfix) with ESMTP id EF6812BD8 for ; Tue, 7 Apr 2020 14:16:40 +0200 (CEST) Received: by mail-lf1-f67.google.com with SMTP id h6so2224149lfc.0 for ; Tue, 07 Apr 2020 05:16:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=semihalf-com.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=Ob7Um5FwhwiLAnDJ6ziAXVJ9309kX0ZX6xiGoZCKv1U=; b=d8lZqeGIqQclOz2HZznFTQdxAESAj3hsFxp89IoTLs2E1o+AEiC6TUsaB5gCF+RKwl REsNCGLPu28yazX+tUkuUTkGFr592vBLXDuk2Z9+pmVMhkuVOCaaxgP0tgKwc6qUzc2V dxa0h4cRxtP5BvEoaf1SR0PRXD0Rn9bW/pY5pxxA2BdzQ3rUDgZbxpKEYIovQe1OaMQt Q4c3VLoj157ybs2qjDYPOB8713BW4WJ1NbpBx/Ih9Ltr60ZHP0/Y5VCe2OsRMH53VIZ+ u6p4ZY5dGCzuk4AsK36M7mUCWw2o/YVW9r1rxSM+XOsA+Qs1B8MTDjYSKiIJUCZGciil jTKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=Ob7Um5FwhwiLAnDJ6ziAXVJ9309kX0ZX6xiGoZCKv1U=; b=GL45xsNFvxMw4To9fWPLGMtbwkqoUz3syuTEL/Xs6rZdahi0AC6nvbx9XWLWBTfVBP oZPfltpL5bTKRu1AKKtPbWAykCdDxG039tR9i95YGhNhbFyDXRPBkIm4sqpuBOoO4pKd diUcnxp4mY9B4GZOnnHWQrZRdGvW59qm4hZNm5LTFMdQ/dhynqJAACPQ+T6wjX8SzqSj ooAWpNuT4b+nxrTPfyvuIwScY69hYqozlQET0y/wRtMazipUXtE+N00JLPgcj/7GFp6I X5e5KkhgzCIDqVQkIhBtU/yGlDAvPhYgmc8oYXThzQQc/NlCWmdB9ulorxrsxt+s+UKa Y7kQ== X-Gm-Message-State: AGi0PubrFovEosXZWMK/+a2hISEwW96LJJOepdCd9geuQKo1qY8QW7mB 7phH2K6Rf2OLs1F1NH2olC6pmylkdAE= X-Google-Smtp-Source: APiQypLWWGhkpEuR+IcGvE3R1JtI3BgYQ9alfUuv5T3vMJgoTdNiYXaoVcbj/IbioiyOfwrRB2MiLA== X-Received: by 2002:ac2:46d3:: with SMTP id p19mr1341682lfo.72.1586261799939; Tue, 07 Apr 2020 05:16:39 -0700 (PDT) Received: from [192.168.8.100] (user-5-173-33-152.play-internet.pl. [5.173.33.152]) by smtp.gmail.com with ESMTPSA id i4sm13277397lfl.57.2020.04.07.05.16.39 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 07 Apr 2020 05:16:39 -0700 (PDT) To: dev@dpdk.org References: <20200331192945.2466880-1-jerinj@marvell.com> <20200405085613.1336841-1-jerinj@marvell.com> <20200405085613.1336841-6-jerinj@marvell.com> From: Andrzej Ostruszka Message-ID: <097e35c5-ffb0-854c-12b6-184849f2d922@semihalf.com> Date: Tue, 7 Apr 2020 14:16:38 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Firefox/68.0 Thunderbird/68.4.1 MIME-Version: 1.0 In-Reply-To: <20200405085613.1336841-6-jerinj@marvell.com> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: Re: [dpdk-dev] [PATCH v4 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" On 4/5/20 10:55 AM, jerinj@marvell.com wrote: > 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 > --- [...]> +/* 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; > +} In general, I'd expect such warnings/errors to be at usage - this is simple test and its job should be just return true/false. But in this particular case I guess it is always an error (no cycles in graph allowed) so I'm fine if you leave it here. > + > +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; > +} [...] > +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; > +} What is the purpose of this function? It looks like just marking as visited. Then maybe change the name to graph_mark_bfs() or something like that. > + > +/* 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; You don't want to clear visited because it will not be used or cleared on next call? With regards Andrzej Ostruszka