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 static struct rte_graph *
 214 graph_mem_fixup_node_ctx(struct rte_graph *graph)
 215 {
 216         struct rte_node *node;
 217         struct node *node_db;
 218         rte_graph_off_t off;
 219         rte_node_t count;
 220         const char *name;
 221
 222         rte_graph_foreach_node(count, off, graph, node) {
 223                 if (node->parent_id == RTE_NODE_ID_INVALID) /* Static node */
 224                         name = node->name;
 225                 else /* Cloned node */
 226                         name = node->parent;
 227
 228                 node_db = node_from_name(name);
 229                 if (node_db == NULL)
 230                         SET_ERR_JMP(ENOLINK, fail, "Node %s not found", name);
 231                 node->process = node_db->process;
 232         }
 233
 234         return graph;
 235 fail:
 236         return NULL;
 237 }
 238
 239 static struct rte_graph *
 240 graph_mem_fixup_secondary(struct rte_graph *graph)
 241 {
 242         if (graph == NULL || rte_eal_process_type() == RTE_PROC_PRIMARY)
 243                 return graph;
 244
 245         return graph_mem_fixup_node_ctx(graph);
 246 }
 247
 248 struct rte_graph *
 249 rte_graph_lookup(const char *name)
 250 {
 251         const struct rte_memzone *mz;
 252         struct rte_graph *rc = NULL;
 253
 254         mz = rte_memzone_lookup(name);
 255         if (mz)
 256                 rc = mz->addr;
 257
 258         return graph_mem_fixup_secondary(rc);
 259 }
 260
 261 rte_graph_t
 262 rte_graph_create(const char *name, struct rte_graph_param *prm)
 263 {
 264         rte_node_t src_node_count;
 265         struct graph *graph;
 266         const char *pattern;
 267         uint16_t i;
 268
 269         graph_spinlock_lock();
 270
 271         /* Check arguments sanity */
 272         if (prm == NULL)
 273                 SET_ERR_JMP(EINVAL, fail, "Param should not be NULL");
 274
 275         if (name == NULL)
 276                 SET_ERR_JMP(EINVAL, fail, "Graph name should not be NULL");
 277
 278         /* Check for existence of duplicate graph */
 279         STAILQ_FOREACH(graph, &graph_list, next)
 280                 if (strncmp(name, graph->name, RTE_GRAPH_NAMESIZE) == 0)
 281                         SET_ERR_JMP(EEXIST, fail, "Found duplicate graph %s",
 282                                     name);
 283
 284         /* Create graph object */
 285         graph = calloc(1, sizeof(*graph));
 286         if (graph == NULL)
 287                 SET_ERR_JMP(ENOMEM, fail, "Failed to calloc graph object");
 288
 289         /* Initialize the graph object */
 290         STAILQ_INIT(&graph->node_list);
 291         if (rte_strscpy(graph->name, name, RTE_GRAPH_NAMESIZE) < 0)
 292                 SET_ERR_JMP(E2BIG, free, "Too big name=%s", name);
 293
 294         /* Expand node pattern and add the nodes to the graph */
 295         for (i = 0; i < prm->nb_node_patterns; i++) {
 296                 pattern = prm->node_patterns[i];
 297                 if (expand_pattern_to_node(graph, pattern))
 298                         goto graph_cleanup;
 299         }
 300
 301         /* Go over all the nodes edges and add them to the graph */
 302         if (graph_node_edges_add(graph))
 303                 goto graph_cleanup;
 304
 305         /* Update adjacency list of all nodes in the graph */
 306         if (graph_adjacency_list_update(graph))
 307                 goto graph_cleanup;
 308
 309         /* Make sure at least a source node present in the graph */
 310         src_node_count = graph_src_nodes_count(graph);
 311         if (src_node_count == 0)
 312                 goto graph_cleanup;
 313
 314         /* Make sure no node is pointing to source node */
 315         if (graph_node_has_edge_to_src_node(graph))
 316                 goto graph_cleanup;
 317
 318         /* Don't allow node has loop to self */
 319         if (graph_node_has_loop_edge(graph))
 320                 goto graph_cleanup;
 321
 322         /* Do BFS from src nodes on the graph to find isolated nodes */
 323         if (graph_has_isolated_node(graph))
 324                 goto graph_cleanup;
 325
 326         /* Initialize graph object */
 327         graph->socket = prm->socket_id;
 328         graph->src_node_count = src_node_count;
 329         graph->node_count = graph_nodes_count(graph);
 330         graph->id = graph_id;
 331
 332         /* Allocate the Graph fast path memory and populate the data */
 333         if (graph_fp_mem_create(graph))
 334                 goto graph_cleanup;
 335
 336         /* Call init() of the all the nodes in the graph */
 337         if (graph_node_init(graph))
 338                 goto graph_mem_destroy;
 339
 340         /* All good, Lets add the graph to the list */
 341         graph_id++;
 342         STAILQ_INSERT_TAIL(&graph_list, graph, next);
 343
 344         graph_spinlock_unlock();
 345         return graph->id;
 346
 347 graph_mem_destroy:
 348         graph_fp_mem_destroy(graph);
 349 graph_cleanup:
 350         graph_cleanup(graph);
 351 free:
 352         free(graph);
 353 fail:
 354         graph_spinlock_unlock();
 355         return RTE_GRAPH_ID_INVALID;
 356 }
 357
 358 int
 359 rte_graph_destroy(rte_graph_t id)
 360 {
 361         struct graph *graph, *tmp;
 362         int rc = -ENOENT;
 363
 364         graph_spinlock_lock();
 365
 366         graph = STAILQ_FIRST(&graph_list);
 367         while (graph != NULL) {
 368                 tmp = STAILQ_NEXT(graph, next);
 369                 if (graph->id == id) {
 370                         /* Call fini() of the all the nodes in the graph */
 371                         graph_node_fini(graph);
 372                         /* Destroy graph fast path memory */
 373                         rc = graph_fp_mem_destroy(graph);
 374                         if (rc)
 375                                 SET_ERR_JMP(rc, done, "Graph %s destroy failed",
 376                                             graph->name);
 377
 378                         graph_cleanup(graph);
 379                         STAILQ_REMOVE(&graph_list, graph, graph, next);
 380                         free(graph);
 381                         graph_id--;
 382                         goto done;
 383                 }
 384                 graph = tmp;
 385         }
 386 done:
 387         graph_spinlock_unlock();
 388         return rc;
 389 }
 390
 391 rte_graph_t
 392 rte_graph_from_name(const char *name)
 393 {
 394         struct graph *graph;
 395
 396         STAILQ_FOREACH(graph, &graph_list, next)
 397                 if (strncmp(graph->name, name, RTE_GRAPH_NAMESIZE) == 0)
 398                         return graph->id;
 399
 400         return RTE_GRAPH_ID_INVALID;
 401 }
 402
 403 char *
 404 rte_graph_id_to_name(rte_graph_t id)
 405 {
 406         struct graph *graph;
 407
 408         GRAPH_ID_CHECK(id);
 409         STAILQ_FOREACH(graph, &graph_list, next)
 410                 if (graph->id == id)
 411                         return graph->name;
 412
 413 fail:
 414         return NULL;
 415 }
 416
 417 struct rte_node *
 418 rte_graph_node_get(rte_graph_t gid, uint32_t nid)
 419 {
 420         struct rte_node *node;
 421         struct graph *graph;
 422         rte_graph_off_t off;
 423         rte_node_t count;
 424
 425         GRAPH_ID_CHECK(gid);
 426         STAILQ_FOREACH(graph, &graph_list, next)
 427                 if (graph->id == gid) {
 428                         rte_graph_foreach_node(count, off, graph->graph,
 429                                                 node) {
 430                                 if (node->id == nid)
 431                                         return node;
 432                         }
 433                         break;
 434                 }
 435 fail:
 436         return NULL;
 437 }
 438
 439 struct rte_node *
 440 rte_graph_node_get_by_name(const char *graph_name, const char *node_name)
 441 {
 442         struct rte_node *node;
 443         struct graph *graph;
 444         rte_graph_off_t off;
 445         rte_node_t count;
 446
 447         STAILQ_FOREACH(graph, &graph_list, next)
 448                 if (!strncmp(graph->name, graph_name, RTE_GRAPH_NAMESIZE)) {
 449                         rte_graph_foreach_node(count, off, graph->graph,
 450                                                 node) {
 451                                 if (!strncmp(node->name, node_name,
 452                                              RTE_NODE_NAMESIZE))
 453                                         return node;
 454                         }
 455                         break;
 456                 }
 457
 458         return NULL;
 459 }
 460
 461 void __rte_noinline
 462 __rte_node_stream_alloc(struct rte_graph *graph, struct rte_node *node)
 463 {
 464         uint16_t size = node->size;
 465
 466         RTE_VERIFY(size != UINT16_MAX);
 467         /* Allocate double amount of size to avoid immediate realloc */
 468         size = RTE_MIN(UINT16_MAX, RTE_MAX(RTE_GRAPH_BURST_SIZE, size * 2));
 469         node->objs = rte_realloc_socket(node->objs, size * sizeof(void *),
 470                                         RTE_CACHE_LINE_SIZE, graph->socket);
 471         RTE_VERIFY(node->objs);
 472         node->size = size;
 473         node->realloc_count++;
 474 }
 475
 476 void __rte_noinline
 477 __rte_node_stream_alloc_size(struct rte_graph *graph, struct rte_node *node,
 478                              uint16_t req_size)
 479 {
 480         uint16_t size = node->size;
 481
 482         RTE_VERIFY(size != UINT16_MAX);
 483         /* Allocate double amount of size to avoid immediate realloc */
 484         size = RTE_MIN(UINT16_MAX, RTE_MAX(RTE_GRAPH_BURST_SIZE, req_size * 2));
 485         node->objs = rte_realloc_socket(node->objs, size * sizeof(void *),
 486                                         RTE_CACHE_LINE_SIZE, graph->socket);
 487         RTE_VERIFY(node->objs);
 488         node->size = size;
 489         node->realloc_count++;
 490 }
 491
 492 static int
 493 graph_to_dot(FILE *f, struct graph *graph)
 494 {
 495         const char *src_edge_color = " [color=blue]\n";
 496         const char *edge_color = "\n";
 497         struct graph_node *graph_node;
 498         char *node_name;
 499         rte_edge_t i;
 500         int rc;
 501
 502         rc = fprintf(f, "Digraph %s {\n\trankdir=LR;\n", graph->name);
 503         if (rc < 0)
 504                 goto end;
 505
 506         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 507                 node_name = graph_node->node->name;
 508                 for (i = 0; i < graph_node->node->nb_edges; i++) {
 509                         rc = fprintf(f, "\t\"%s\"->\"%s\"%s", node_name,
 510                                      graph_node->adjacency_list[i]->node->name,
 511                                      graph_node->node->flags & RTE_NODE_SOURCE_F
 512                                              ? src_edge_color
 513                                              : edge_color);
 514                         if (rc < 0)
 515                                 goto end;
 516                 }
 517         }
 518         rc = fprintf(f, "}\n");
 519         if (rc < 0)
 520                 goto end;
 521
 522         return 0;
 523 end:
 524         rte_errno = EBADF;
 525         return -rte_errno;
 526 }
 527
 528 int
 529 rte_graph_export(const char *name, FILE *f)
 530 {
 531         struct graph *graph;
 532         int rc = ENOENT;
 533
 534         STAILQ_FOREACH(graph, &graph_list, next) {
 535                 if (strncmp(graph->name, name, RTE_GRAPH_NAMESIZE) == 0) {
 536                         rc = graph_to_dot(f, graph);
 537                         goto end;
 538                 }
 539         }
 540 end:
 541         return -rc;
 542 }
 543
 544 static void
 545 graph_scan_dump(FILE *f, rte_graph_t id, bool all)
 546 {
 547         struct graph *graph;
 548
 549         RTE_VERIFY(f);
 550         GRAPH_ID_CHECK(id);
 551
 552         STAILQ_FOREACH(graph, &graph_list, next) {
 553                 if (all == true) {
 554                         graph_dump(f, graph);
 555                 } else if (graph->id == id) {
 556                         graph_dump(f, graph);
 557                         return;
 558                 }
 559         }
 560 fail:
 561         return;
 562 }
 563
 564 void
 565 rte_graph_dump(FILE *f, rte_graph_t id)
 566 {
 567         graph_scan_dump(f, id, false);
 568 }
 569
 570 void
 571 rte_graph_list_dump(FILE *f)
 572 {
 573         graph_scan_dump(f, 0, true);
 574 }
 575
 576 rte_graph_t
 577 rte_graph_max_count(void)
 578 {
 579         return graph_id;
 580 }
 581
 582 RTE_LOG_REGISTER(rte_graph_logtype, lib.graph, INFO);