lib/librte_graph/graph.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(C) 2020 Marvell International Ltd.
   3  */
   4
   5 #include <fnmatch.h>
   6 #include <stdbool.h>
   7
   8 #include <rte_common.h>
   9 #include <rte_debug.h>
  10 #include <rte_errno.h>
  11 #include <rte_malloc.h>
  12 #include <rte_memzone.h>
  13 #include <rte_spinlock.h>
  14 #include <rte_string_fns.h>
  15
  16 #include "graph_private.h"
  17
  18 static struct graph_head graph_list = STAILQ_HEAD_INITIALIZER(graph_list);
  19 static rte_spinlock_t graph_lock = RTE_SPINLOCK_INITIALIZER;
  20 static rte_graph_t graph_id;
  21 int rte_graph_logtype;
  22
  23 #define GRAPH_ID_CHECK(id) ID_CHECK(id, graph_id)
  24
  25 /* Private functions */
  26 struct graph_head *
  27 graph_list_head_get(void)
  28 {
  29         return &graph_list;
  30 }
  31
  32 void
  33 graph_spinlock_lock(void)
  34 {
  35         rte_spinlock_lock(&graph_lock);
  36 }
  37
  38 void
  39 graph_spinlock_unlock(void)
  40 {
  41         rte_spinlock_unlock(&graph_lock);
  42 }
  43
  44 static int
  45 graph_node_add(struct graph *graph, struct node *node)
  46 {
  47         struct graph_node *graph_node;
  48         size_t sz;
  49
  50         /* Skip the duplicate nodes */
  51         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  52                 if (strncmp(node->name, graph_node->node->name,
  53                             RTE_NODE_NAMESIZE) == 0)
  54                         return 0;
  55
  56         /* Allocate new graph node object */
  57         sz = sizeof(*graph_node) + node->nb_edges * sizeof(struct node *);
  58         graph_node = calloc(1, sz);
  59
  60         if (graph_node == NULL)
  61                 SET_ERR_JMP(ENOMEM, free, "Failed to calloc %s object",
  62                             node->name);
  63
  64         /* Initialize the graph node */
  65         graph_node->node = node;
  66
  67         /* Add to graph node list */
  68         STAILQ_INSERT_TAIL(&graph->node_list, graph_node, next);
  69         return 0;
  70
  71 free:
  72         free(graph_node);
  73         return -rte_errno;
  74 }
  75
  76 static struct graph_node *
  77 node_to_graph_node(struct graph *graph, struct node *node)
  78 {
  79         struct graph_node *graph_node;
  80
  81         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  82                 if (graph_node->node == node)
  83                         return graph_node;
  84
  85         SET_ERR_JMP(ENODEV, fail, "Found isolated node %s", node->name);
  86 fail:
  87         return NULL;
  88 }
  89
  90 static int
  91 graph_node_edges_add(struct graph *graph)
  92 {
  93         struct graph_node *graph_node;
  94         struct node *adjacency;
  95         const char *next;
  96         rte_edge_t i;
  97
  98         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
  99                 for (i = 0; i < graph_node->node->nb_edges; i++) {
 100                         next = graph_node->node->next_nodes[i];
 101                         adjacency = node_from_name(next);
 102                         if (adjacency == NULL)
 103                                 SET_ERR_JMP(EINVAL, fail,
 104                                             "Node %s not registered", next);
 105                         if (graph_node_add(graph, adjacency))
 106                                 goto fail;
 107                 }
 108         }
 109         return 0;
 110 fail:
 111         return -rte_errno;
 112 }
 113
 114 static int
 115 graph_adjacency_list_update(struct graph *graph)
 116 {
 117         struct graph_node *graph_node, *tmp;
 118         struct node *adjacency;
 119         const char *next;
 120         rte_edge_t i;
 121
 122         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 123                 for (i = 0; i < graph_node->node->nb_edges; i++) {
 124                         next = graph_node->node->next_nodes[i];
 125                         adjacency = node_from_name(next);
 126                         if (adjacency == NULL)
 127                                 SET_ERR_JMP(EINVAL, fail,
 128                                             "Node %s not registered", next);
 129                         tmp = node_to_graph_node(graph, adjacency);
 130                         if (tmp == NULL)
 131                                 goto fail;
 132                         graph_node->adjacency_list[i] = tmp;
 133                 }
 134         }
 135
 136         return 0;
 137 fail:
 138         return -rte_errno;
 139 }
 140
 141 static int
 142 expand_pattern_to_node(struct graph *graph, const char *pattern)
 143 {
 144         struct node_head *node_head = node_list_head_get();
 145         bool found = false;
 146         struct node *node;
 147
 148         /* Check for pattern match */
 149         STAILQ_FOREACH(node, node_head, next) {
 150                 if (fnmatch(pattern, node->name, 0) == 0) {
 151                         if (graph_node_add(graph, node))
 152                                 goto fail;
 153                         found = true;
 154                 }
 155         }
 156         if (found == false)
 157                 SET_ERR_JMP(EFAULT, fail, "Pattern %s node not found", pattern);
 158
 159         return 0;
 160 fail:
 161         return -rte_errno;
 162 }
 163
 164 static void
 165 graph_cleanup(struct graph *graph)
 166 {
 167         struct graph_node *graph_node;
 168
 169         while (!STAILQ_EMPTY(&graph->node_list)) {
 170                 graph_node = STAILQ_FIRST(&graph->node_list);
 171                 STAILQ_REMOVE_HEAD(&graph->node_list, next);
 172                 free(graph_node);
 173         }
 174 }
 175
 176 static int
 177 graph_node_init(struct graph *graph)
 178 {
 179         struct graph_node *graph_node;
 180         const char *name;
 181         int rc;
 182
 183         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 184                 if (graph_node->node->init) {
 185                         name = graph_node->node->name;
 186                         rc = graph_node->node->init(
 187                                 graph->graph,
 188                                 graph_node_name_to_ptr(graph->graph, name));
 189                         if (rc)
 190                                 SET_ERR_JMP(rc, err, "Node %s init() failed",
 191                                             name);
 192                 }
 193         }
 194
 195         return 0;
 196 err:
 197         return -rte_errno;
 198 }
 199
 200 static void
 201 graph_node_fini(struct graph *graph)
 202 {
 203         struct graph_node *graph_node;
 204
 205         STAILQ_FOREACH(graph_node, &graph->node_list, next)
 206                 if (graph_node->node->fini)
 207                         graph_node->node->fini(
 208                                 graph->graph,
 209                                 graph_node_name_to_ptr(graph->graph,
 210                                                        graph_node->node->name));
 211 }
 212
 213 rte_graph_t
 214 rte_graph_create(const char *name, struct rte_graph_param *prm)
 215 {
 216         rte_node_t src_node_count;
 217         struct graph *graph;
 218         const char *pattern;
 219         uint16_t i;
 220
 221         graph_spinlock_lock();
 222
 223         /* Check arguments sanity */
 224         if (prm == NULL)
 225                 SET_ERR_JMP(EINVAL, fail, "Param should not be NULL");
 226
 227         if (name == NULL)
 228                 SET_ERR_JMP(EINVAL, fail, "Graph name should not be NULL");
 229
 230         /* Check for existence of duplicate graph */
 231         STAILQ_FOREACH(graph, &graph_list, next)
 232                 if (strncmp(name, graph->name, RTE_GRAPH_NAMESIZE) == 0)
 233                         SET_ERR_JMP(EEXIST, fail, "Found duplicate graph %s",
 234                                     name);
 235
 236         /* Create graph object */
 237         graph = calloc(1, sizeof(*graph));
 238         if (graph == NULL)
 239                 SET_ERR_JMP(ENOMEM, fail, "Failed to calloc graph object");
 240
 241         /* Initialize the graph object */
 242         STAILQ_INIT(&graph->node_list);
 243         if (rte_strscpy(graph->name, name, RTE_GRAPH_NAMESIZE) < 0)
 244                 SET_ERR_JMP(E2BIG, free, "Too big name=%s", name);
 245
 246         /* Expand node pattern and add the nodes to the graph */
 247         for (i = 0; i < prm->nb_node_patterns; i++) {
 248                 pattern = prm->node_patterns[i];
 249                 if (expand_pattern_to_node(graph, pattern))
 250                         goto graph_cleanup;
 251         }
 252
 253         /* Go over all the nodes edges and add them to the graph */
 254         if (graph_node_edges_add(graph))
 255                 goto graph_cleanup;
 256
 257         /* Update adjacency list of all nodes in the graph */
 258         if (graph_adjacency_list_update(graph))
 259                 goto graph_cleanup;
 260
 261         /* Make sure at least a source node present in the graph */
 262         src_node_count = graph_src_nodes_count(graph);
 263         if (src_node_count == 0)
 264                 goto graph_cleanup;
 265
 266         /* Make sure no node is pointing to source node */
 267         if (graph_node_has_edge_to_src_node(graph))
 268                 goto graph_cleanup;
 269
 270         /* Don't allow node has loop to self */
 271         if (graph_node_has_loop_edge(graph))
 272                 goto graph_cleanup;
 273
 274         /* Do BFS from src nodes on the graph to find isolated nodes */
 275         if (graph_has_isolated_node(graph))
 276                 goto graph_cleanup;
 277
 278         /* Initialize graph object */
 279         graph->socket = prm->socket_id;
 280         graph->src_node_count = src_node_count;
 281         graph->node_count = graph_nodes_count(graph);
 282         graph->id = graph_id;
 283
 284         /* Allocate the Graph fast path memory and populate the data */
 285         if (graph_fp_mem_create(graph))
 286                 goto graph_cleanup;
 287
 288         /* Call init() of the all the nodes in the graph */
 289         if (graph_node_init(graph))
 290                 goto graph_mem_destroy;
 291
 292         /* All good, Lets add the graph to the list */
 293         graph_id++;
 294         STAILQ_INSERT_TAIL(&graph_list, graph, next);
 295
 296         graph_spinlock_unlock();
 297         return graph->id;
 298
 299 graph_mem_destroy:
 300         graph_fp_mem_destroy(graph);
 301 graph_cleanup:
 302         graph_cleanup(graph);
 303 free:
 304         free(graph);
 305 fail:
 306         graph_spinlock_unlock();
 307         return RTE_GRAPH_ID_INVALID;
 308 }
 309
 310 int
 311 rte_graph_destroy(rte_graph_t id)
 312 {
 313         struct graph *graph, *tmp;
 314         int rc = -ENOENT;
 315
 316         graph_spinlock_lock();
 317
 318         graph = STAILQ_FIRST(&graph_list);
 319         while (graph != NULL) {
 320                 tmp = STAILQ_NEXT(graph, next);
 321                 if (graph->id == id) {
 322                         /* Call fini() of the all the nodes in the graph */
 323                         graph_node_fini(graph);
 324                         /* Destroy graph fast path memory */
 325                         rc = graph_fp_mem_destroy(graph);
 326                         if (rc)
 327                                 SET_ERR_JMP(rc, done, "Graph %s destroy failed",
 328                                             graph->name);
 329
 330                         graph_cleanup(graph);
 331                         STAILQ_REMOVE(&graph_list, graph, graph, next);
 332                         free(graph);
 333                         graph_id--;
 334                         goto done;
 335                 }
 336                 graph = tmp;
 337         }
 338 done:
 339         graph_spinlock_unlock();
 340         return rc;
 341 }
 342
 343 void __rte_noinline
 344 __rte_node_stream_alloc(struct rte_graph *graph, struct rte_node *node)
 345 {
 346         uint16_t size = node->size;
 347
 348         RTE_VERIFY(size != UINT16_MAX);
 349         /* Allocate double amount of size to avoid immediate realloc */
 350         size = RTE_MIN(UINT16_MAX, RTE_MAX(RTE_GRAPH_BURST_SIZE, size * 2));
 351         node->objs = rte_realloc_socket(node->objs, size * sizeof(void *),
 352                                         RTE_CACHE_LINE_SIZE, graph->socket);
 353         RTE_VERIFY(node->objs);
 354         node->size = size;
 355         node->realloc_count++;
 356 }