1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(C) 2020 Marvell International Ltd. 3 */ 4 5 #include <stdbool.h> 6 #include <string.h> 7 8 #include <rte_errno.h> 9 10 #include "graph_private.h" 11 12 /* Check whether a node has next_node to itself */ 13 static inline int 14 node_has_loop_edge(struct node *node) 15 { 16 rte_edge_t i; 17 char *name; 18 int rc = 0; 19 20 for (i = 0; i < node->nb_edges; i++) { 21 if (strncmp(node->name, node->next_nodes[i], 22 RTE_NODE_NAMESIZE) == 0) { 23 name = node->name; 24 rc = 1; 25 SET_ERR_JMP(EINVAL, fail, "Node %s has loop to self", 26 name); 27 } 28 } 29 fail: 30 return rc; 31 } 32 33 int 34 graph_node_has_loop_edge(struct graph *graph) 35 { 36 struct graph_node *graph_node; 37 38 STAILQ_FOREACH(graph_node, &graph->node_list, next) 39 if (node_has_loop_edge(graph_node->node)) 40 return 1; 41 42 return 0; 43 } 44 45 rte_node_t 46 graph_src_nodes_count(struct graph *graph) 47 { 48 struct graph_node *graph_node; 49 rte_node_t rc = 0; 50 51 STAILQ_FOREACH(graph_node, &graph->node_list, next) 52 if (graph_node->node->flags & RTE_NODE_SOURCE_F) 53 rc++; 54 55 if (rc == 0) 56 SET_ERR_JMP(EINVAL, fail, "Graph needs at least a source node"); 57 fail: 58 return rc; 59 } 60 61 /* Check whether a node has next_node to a source node */ 62 int 63 graph_node_has_edge_to_src_node(struct graph *graph) 64 { 65 struct graph_node *graph_node; 66 struct node *node; 67 rte_edge_t i; 68 69 STAILQ_FOREACH(graph_node, &graph->node_list, next) { 70 for (i = 0; i < graph_node->node->nb_edges; i++) { 71 node = graph_node->adjacency_list[i]->node; 72 if (node->flags & RTE_NODE_SOURCE_F) 73 SET_ERR_JMP( 74 EEXIST, fail, 75 "Node %s points to the source node %s", 76 graph_node->node->name, node->name); 77 } 78 } 79 80 return 0; 81 fail: 82 return 1; 83 } 84 85 rte_node_t 86 graph_nodes_count(struct graph *graph) 87 { 88 struct graph_node *graph_node; 89 rte_node_t count = 0; 90 91 STAILQ_FOREACH(graph_node, &graph->node_list, next) 92 count++; 93 94 return count; 95 } 96 97 void 98 graph_mark_nodes_as_not_visited(struct graph *graph) 99 { 100 struct graph_node *graph_node; 101 102 STAILQ_FOREACH(graph_node, &graph->node_list, next) 103 graph_node->visited = false; 104 } 105 106 int 107 graph_bfs(struct graph *graph, struct graph_node *start) 108 { 109 struct graph_node **queue, *v, *tmp; 110 uint16_t head = 0, tail = 0; 111 rte_edge_t i; 112 size_t sz; 113 114 sz = sizeof(struct graph_node *) * graph_nodes_count(graph); 115 queue = malloc(sz); 116 if (queue == NULL) 117 SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu", 118 sz); 119 120 /* BFS algorithm */ 121 queue[tail++] = start; 122 start->visited = true; 123 while (head != tail) { 124 v = queue[head++]; 125 for (i = 0; i < v->node->nb_edges; i++) { 126 tmp = v->adjacency_list[i]; 127 if (tmp->visited == false) { 128 queue[tail++] = tmp; 129 tmp->visited = true; 130 } 131 } 132 } 133 134 free(queue); 135 return 0; 136 137 fail: 138 return -rte_errno; 139 } 140 141 /* Check whether a node has connected path or parent node */ 142 int 143 graph_has_isolated_node(struct graph *graph) 144 { 145 struct graph_node *graph_node; 146 147 graph_mark_nodes_as_not_visited(graph); 148 149 STAILQ_FOREACH(graph_node, &graph->node_list, next) { 150 if (graph_node->node->flags & RTE_NODE_SOURCE_F) { 151 if (graph_node->node->nb_edges == 0) 152 SET_ERR_JMP(EINVAL, fail, 153 "%s node needs minimum one edge", 154 graph_node->node->name); 155 if (graph_bfs(graph, graph_node)) 156 goto fail; 157 } 158 } 159 160 STAILQ_FOREACH(graph_node, &graph->node_list, next) 161 if (graph_node->visited == false) 162 SET_ERR_JMP(EINVAL, fail, "Found isolated node %s", 163 graph_node->node->name); 164 165 return 0; 166 fail: 167 return 1; 168 } 169