--- /dev/null
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(C) 2020 Marvell International Ltd.
+ */
+
+#include <stdbool.h>
+#include <string.h>
+
+#include <rte_common.h>
+#include <rte_errno.h>
+
+#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;
+}
#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 { \
} \
} while (0)
+#define SET_ERR_JMP(err, where, fmt, ...) \
+ do { \
+ graph_err(fmt, ##__VA_ARGS__); \
+ rte_errno = err; \
+ goto where; \
+ } while (0)
/**
* @internal
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);
*/
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
*/
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
*
git.droids-corp.org / dpdk.git / commitdiff