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
  22 #define GRAPH_ID_CHECK(id) ID_CHECK(id, graph_id)
  23
  24 /* Private functions */
  25 struct graph_head *
  26 graph_list_head_get(void)
  27 {
  28         return &graph_list;
  29 }
  30
  31 void
  32 graph_spinlock_lock(void)
  33 {
  34         rte_spinlock_lock(&graph_lock);
  35 }
  36
  37 void
  38 graph_spinlock_unlock(void)
  39 {
  40         rte_spinlock_unlock(&graph_lock);
  41 }
  42
  43 static int
  44 graph_node_add(struct graph *graph, struct node *node)
  45 {
  46         struct graph_node *graph_node;
  47         size_t sz;
  48
  49         /* Skip the duplicate nodes */
  50         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  51                 if (strncmp(node->name, graph_node->node->name,
  52                             RTE_NODE_NAMESIZE) == 0)
  53                         return 0;
  54
  55         /* Allocate new graph node object */
  56         sz = sizeof(*graph_node) + node->nb_edges * sizeof(struct node *);
  57         graph_node = calloc(1, sz);
  58
  59         if (graph_node == NULL)
  60                 SET_ERR_JMP(ENOMEM, free, "Failed to calloc %s object",
  61                             node->name);
  62
  63         /* Initialize the graph node */
  64         graph_node->node = node;
  65
  66         /* Add to graph node list */
  67         STAILQ_INSERT_TAIL(&graph->node_list, graph_node, next);
  68         return 0;
  69
  70 free:
  71         free(graph_node);
  72         return -rte_errno;
  73 }
  74
  75 static struct graph_node *
  76 node_to_graph_node(struct graph *graph, struct node *node)
  77 {
  78         struct graph_node *graph_node;
  79
  80         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  81                 if (graph_node->node == node)
  82                         return graph_node;
  83
  84         SET_ERR_JMP(ENODEV, fail, "Found isolated node %s", node->name);
  85 fail:
  86         return NULL;
  87 }
  88
  89 static int
  90 graph_node_edges_add(struct graph *graph)
  91 {
  92         struct graph_node *graph_node;
  93         struct node *adjacency;
  94         const char *next;
  95         rte_edge_t i;
  96
  97         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
  98                 for (i = 0; i < graph_node->node->nb_edges; i++) {
  99                         next = graph_node->node->next_nodes[i];
 100                         adjacency = node_from_name(next);
 101                         if (adjacency == NULL)
 102                                 SET_ERR_JMP(EINVAL, fail,
 103                                             "Node %s not registered", next);
 104                         if (graph_node_add(graph, adjacency))
 105                                 goto fail;
 106                 }
 107         }
 108         return 0;
 109 fail:
 110         return -rte_errno;
 111 }
 112
 113 static int
 114 graph_adjacency_list_update(struct graph *graph)
 115 {
 116         struct graph_node *graph_node, *tmp;
 117         struct node *adjacency;
 118         const char *next;
 119         rte_edge_t i;
 120
 121         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 122                 for (i = 0; i < graph_node->node->nb_edges; i++) {
 123                         next = graph_node->node->next_nodes[i];
 124                         adjacency = node_from_name(next);
 125                         if (adjacency == NULL)
 126                                 SET_ERR_JMP(EINVAL, fail,
 127                                             "Node %s not registered", next);
 128                         tmp = node_to_graph_node(graph, adjacency);
 129                         if (tmp == NULL)
 130                                 goto fail;
 131                         graph_node->adjacency_list[i] = tmp;
 132                 }
 133         }
 134
 135         return 0;
 136 fail:
 137         return -rte_errno;
 138 }
 139
 140 static int
 141 expand_pattern_to_node(struct graph *graph, const char *pattern)
 142 {
 143         struct node_head *node_head = node_list_head_get();
 144         bool found = false;
 145         struct node *node;
 146
 147         /* Check for pattern match */
 148         STAILQ_FOREACH(node, node_head, next) {
 149                 if (fnmatch(pattern, node->name, 0) == 0) {
 150                         if (graph_node_add(graph, node))
 151                                 goto fail;
 152                         found = true;
 153                 }
 154         }
 155         if (found == false)
 156                 SET_ERR_JMP(EFAULT, fail, "Pattern %s node not found", pattern);
 157
 158         return 0;
 159 fail:
 160         return -rte_errno;
 161 }
 162
 163 static void
 164 graph_cleanup(struct graph *graph)
 165 {
 166         struct graph_node *graph_node;
 167
 168         while (!STAILQ_EMPTY(&graph->node_list)) {
 169                 graph_node = STAILQ_FIRST(&graph->node_list);
 170                 STAILQ_REMOVE_HEAD(&graph->node_list, next);
 171                 free(graph_node);
 172         }
 173 }
 174
 175 static int
 176 graph_node_init(struct graph *graph)
 177 {
 178         struct graph_node *graph_node;
 179         const char *name;
 180         int rc;
 181
 182         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 183                 if (graph_node->node->init) {
 184                         name = graph_node->node->name;
 185                         rc = graph_node->node->init(
 186                                 graph->graph,
 187                                 graph_node_name_to_ptr(graph->graph, name));
 188                         if (rc)
 189                                 SET_ERR_JMP(rc, err, "Node %s init() failed",
 190                                             name);
 191                 }
 192         }
 193
 194         return 0;
 195 err:
 196         return -rte_errno;
 197 }
 198
 199 static void
 200 graph_node_fini(struct graph *graph)
 201 {
 202         struct graph_node *graph_node;
 203
 204         STAILQ_FOREACH(graph_node, &graph->node_list, next)
 205                 if (graph_node->node->fini)
 206                         graph_node->node->fini(
 207                                 graph->graph,
 208                                 graph_node_name_to_ptr(graph->graph,
 209                                                        graph_node->node->name));
 210 }
 211
 212 static struct rte_graph *
 213 graph_mem_fixup_node_ctx(struct rte_graph *graph)
 214 {
 215         struct rte_node *node;
 216         struct node *node_db;
 217         rte_graph_off_t off;
 218         rte_node_t count;
 219         const char *name;
 220
 221         rte_graph_foreach_node(count, off, graph, node) {
 222                 if (node->parent_id == RTE_NODE_ID_INVALID) /* Static node */
 223                         name = node->name;
 224                 else /* Cloned node */
 225                         name = node->parent;
 226
 227                 node_db = node_from_name(name);
 228                 if (node_db == NULL)
 229                         SET_ERR_JMP(ENOLINK, fail, "Node %s not found", name);
 230                 node->process = node_db->process;
 231         }
 232
 233         return graph;
 234 fail:
 235         return NULL;
 236 }
 237
 238 static struct rte_graph *
 239 graph_mem_fixup_secondary(struct rte_graph *graph)
 240 {
 241         if (graph == NULL || rte_eal_process_type() == RTE_PROC_PRIMARY)
 242                 return graph;
 243
 244         return graph_mem_fixup_node_ctx(graph);
 245 }
 246
 247 struct rte_graph *
 248 rte_graph_lookup(const char *name)
 249 {
 250         const struct rte_memzone *mz;
 251         struct rte_graph *rc = NULL;
 252
 253         mz = rte_memzone_lookup(name);
 254         if (mz)
 255                 rc = mz->addr;
 256
 257         return graph_mem_fixup_secondary(rc);
 258 }
 259
 260 rte_graph_t
 261 rte_graph_create(const char *name, struct rte_graph_param *prm)
 262 {
 263         rte_node_t src_node_count;
 264         struct graph *graph;
 265         const char *pattern;
 266         uint16_t i;
 267
 268         graph_spinlock_lock();
 269
 270         /* Check arguments sanity */
 271         if (prm == NULL)
 272                 SET_ERR_JMP(EINVAL, fail, "Param should not be NULL");
 273
 274         if (name == NULL)
 275                 SET_ERR_JMP(EINVAL, fail, "Graph name should not be NULL");
 276
 277         /* Check for existence of duplicate graph */
 278         STAILQ_FOREACH(graph, &graph_list, next)
 279                 if (strncmp(name, graph->name, RTE_GRAPH_NAMESIZE) == 0)
 280                         SET_ERR_JMP(EEXIST, fail, "Found duplicate graph %s",
 281                                     name);
 282
 283         /* Create graph object */
 284         graph = calloc(1, sizeof(*graph));
 285         if (graph == NULL)
 286                 SET_ERR_JMP(ENOMEM, fail, "Failed to calloc graph object");
 287
 288         /* Initialize the graph object */
 289         STAILQ_INIT(&graph->node_list);
 290         if (rte_strscpy(graph->name, name, RTE_GRAPH_NAMESIZE) < 0)
 291                 SET_ERR_JMP(E2BIG, free, "Too big name=%s", name);
 292
 293         /* Expand node pattern and add the nodes to the graph */
 294         for (i = 0; i < prm->nb_node_patterns; i++) {
 295                 pattern = prm->node_patterns[i];
 296                 if (expand_pattern_to_node(graph, pattern))
 297                         goto graph_cleanup;
 298         }
 299
 300         /* Go over all the nodes edges and add them to the graph */
 301         if (graph_node_edges_add(graph))
 302                 goto graph_cleanup;
 303
 304         /* Update adjacency list of all nodes in the graph */
 305         if (graph_adjacency_list_update(graph))
 306                 goto graph_cleanup;
 307
 308         /* Make sure at least a source node present in the graph */
 309         src_node_count = graph_src_nodes_count(graph);
 310         if (src_node_count == 0)
 311                 goto graph_cleanup;
 312
 313         /* Make sure no node is pointing to source node */
 314         if (graph_node_has_edge_to_src_node(graph))
 315                 goto graph_cleanup;
 316
 317         /* Don't allow node has loop to self */
 318         if (graph_node_has_loop_edge(graph))
 319                 goto graph_cleanup;
 320
 321         /* Do BFS from src nodes on the graph to find isolated nodes */
 322         if (graph_has_isolated_node(graph))
 323                 goto graph_cleanup;
 324
 325         /* Initialize graph object */
 326         graph->socket = prm->socket_id;
 327         graph->src_node_count = src_node_count;
 328         graph->node_count = graph_nodes_count(graph);
 329         graph->id = graph_id;
 330
 331         /* Allocate the Graph fast path memory and populate the data */
 332         if (graph_fp_mem_create(graph))
 333                 goto graph_cleanup;
 334
 335         /* Call init() of the all the nodes in the graph */
 336         if (graph_node_init(graph))
 337                 goto graph_mem_destroy;
 338
 339         /* All good, Lets add the graph to the list */
 340         graph_id++;
 341         STAILQ_INSERT_TAIL(&graph_list, graph, next);
 342
 343         graph_spinlock_unlock();
 344         return graph->id;
 345
 346 graph_mem_destroy:
 347         graph_fp_mem_destroy(graph);
 348 graph_cleanup:
 349         graph_cleanup(graph);
 350 free:
 351         free(graph);
 352 fail:
 353         graph_spinlock_unlock();
 354         return RTE_GRAPH_ID_INVALID;
 355 }
 356
 357 int
 358 rte_graph_destroy(rte_graph_t id)
 359 {
 360         struct graph *graph, *tmp;
 361         int rc = -ENOENT;
 362
 363         graph_spinlock_lock();
 364
 365         graph = STAILQ_FIRST(&graph_list);
 366         while (graph != NULL) {
 367                 tmp = STAILQ_NEXT(graph, next);
 368                 if (graph->id == id) {
 369                         /* Call fini() of the all the nodes in the graph */
 370                         graph_node_fini(graph);
 371                         /* Destroy graph fast path memory */
 372                         rc = graph_fp_mem_destroy(graph);
 373                         if (rc)
 374                                 SET_ERR_JMP(rc, done, "Graph %s destroy failed",
 375                                             graph->name);
 376
 377                         graph_cleanup(graph);
 378                         STAILQ_REMOVE(&graph_list, graph, graph, next);
 379                         free(graph);
 380                         graph_id--;
 381                         goto done;
 382                 }
 383                 graph = tmp;
 384         }
 385 done:
 386         graph_spinlock_unlock();
 387         return rc;
 388 }
 389
 390 rte_graph_t
 391 rte_graph_from_name(const char *name)
 392 {
 393         struct graph *graph;
 394
 395         STAILQ_FOREACH(graph, &graph_list, next)
 396                 if (strncmp(graph->name, name, RTE_GRAPH_NAMESIZE) == 0)
 397                         return graph->id;
 398
 399         return RTE_GRAPH_ID_INVALID;
 400 }
 401
 402 char *
 403 rte_graph_id_to_name(rte_graph_t id)
 404 {
 405         struct graph *graph;
 406
 407         GRAPH_ID_CHECK(id);
 408         STAILQ_FOREACH(graph, &graph_list, next)
 409                 if (graph->id == id)
 410                         return graph->name;
 411
 412 fail:
 413         return NULL;
 414 }
 415
 416 struct rte_node *
 417 rte_graph_node_get(rte_graph_t gid, uint32_t nid)
 418 {
 419         struct rte_node *node;
 420         struct graph *graph;
 421         rte_graph_off_t off;
 422         rte_node_t count;
 423
 424         GRAPH_ID_CHECK(gid);
 425         STAILQ_FOREACH(graph, &graph_list, next)
 426                 if (graph->id == gid) {
 427                         rte_graph_foreach_node(count, off, graph->graph,
 428                                                 node) {
 429                                 if (node->id == nid)
 430                                         return node;
 431                         }
 432                         break;
 433                 }
 434 fail:
 435         return NULL;
 436 }
 437
 438 struct rte_node *
 439 rte_graph_node_get_by_name(const char *graph_name, const char *node_name)
 440 {
 441         struct rte_node *node;
 442         struct graph *graph;
 443         rte_graph_off_t off;
 444         rte_node_t count;
 445
 446         STAILQ_FOREACH(graph, &graph_list, next)
 447                 if (!strncmp(graph->name, graph_name, RTE_GRAPH_NAMESIZE)) {
 448                         rte_graph_foreach_node(count, off, graph->graph,
 449                                                 node) {
 450                                 if (!strncmp(node->name, node_name,
 451                                              RTE_NODE_NAMESIZE))
 452                                         return node;
 453                         }
 454                         break;
 455                 }
 456
 457         return NULL;
 458 }
 459
 460 void __rte_noinline
 461 __rte_node_stream_alloc(struct rte_graph *graph, struct rte_node *node)
 462 {
 463         uint16_t size = node->size;
 464
 465         RTE_VERIFY(size != UINT16_MAX);
 466         /* Allocate double amount of size to avoid immediate realloc */
 467         size = RTE_MIN(UINT16_MAX, RTE_MAX(RTE_GRAPH_BURST_SIZE, size * 2));
 468         node->objs = rte_realloc_socket(node->objs, size * sizeof(void *),
 469                                         RTE_CACHE_LINE_SIZE, graph->socket);
 470         RTE_VERIFY(node->objs);
 471         node->size = size;
 472         node->realloc_count++;
 473 }
 474
 475 void __rte_noinline
 476 __rte_node_stream_alloc_size(struct rte_graph *graph, struct rte_node *node,
 477                              uint16_t req_size)
 478 {
 479         uint16_t size = node->size;
 480
 481         RTE_VERIFY(size != UINT16_MAX);
 482         /* Allocate double amount of size to avoid immediate realloc */
 483         size = RTE_MIN(UINT16_MAX, RTE_MAX(RTE_GRAPH_BURST_SIZE, req_size * 2));
 484         node->objs = rte_realloc_socket(node->objs, size * sizeof(void *),
 485                                         RTE_CACHE_LINE_SIZE, graph->socket);
 486         RTE_VERIFY(node->objs);
 487         node->size = size;
 488         node->realloc_count++;
 489 }
 490
 491 static int
 492 graph_to_dot(FILE *f, struct graph *graph)
 493 {
 494         const char *src_edge_color = " [color=blue]\n";
 495         const char *edge_color = "\n";
 496         struct graph_node *graph_node;
 497         char *node_name;
 498         rte_edge_t i;
 499         int rc;
 500
 501         rc = fprintf(f, "Digraph %s {\n\trankdir=LR;\n", graph->name);
 502         if (rc < 0)
 503                 goto end;
 504
 505         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 506                 node_name = graph_node->node->name;
 507                 for (i = 0; i < graph_node->node->nb_edges; i++) {
 508                         rc = fprintf(f, "\t\"%s\"->\"%s\"%s", node_name,
 509                                      graph_node->adjacency_list[i]->node->name,
 510                                      graph_node->node->flags & RTE_NODE_SOURCE_F
 511                                              ? src_edge_color
 512                                              : edge_color);
 513                         if (rc < 0)
 514                                 goto end;
 515                 }
 516         }
 517         rc = fprintf(f, "}\n");
 518         if (rc < 0)
 519                 goto end;
 520
 521         return 0;
 522 end:
 523         rte_errno = EBADF;
 524         return -rte_errno;
 525 }
 526
 527 int
 528 rte_graph_export(const char *name, FILE *f)
 529 {
 530         struct graph *graph;
 531         int rc = ENOENT;
 532
 533         STAILQ_FOREACH(graph, &graph_list, next) {
 534                 if (strncmp(graph->name, name, RTE_GRAPH_NAMESIZE) == 0) {
 535                         rc = graph_to_dot(f, graph);
 536                         goto end;
 537                 }
 538         }
 539 end:
 540         return -rc;
 541 }
 542
 543 static void
 544 graph_scan_dump(FILE *f, rte_graph_t id, bool all)
 545 {
 546         struct graph *graph;
 547
 548         RTE_VERIFY(f);
 549         GRAPH_ID_CHECK(id);
 550
 551         STAILQ_FOREACH(graph, &graph_list, next) {
 552                 if (all == true) {
 553                         graph_dump(f, graph);
 554                 } else if (graph->id == id) {
 555                         graph_dump(f, graph);
 556                         return;
 557                 }
 558         }
 559 fail:
 560         return;
 561 }
 562
 563 void
 564 rte_graph_dump(FILE *f, rte_graph_t id)
 565 {
 566         graph_scan_dump(f, id, false);
 567 }
 568
 569 void
 570 rte_graph_list_dump(FILE *f)
 571 {
 572         graph_scan_dump(f, 0, true);
 573 }
 574
 575 rte_graph_t
 576 rte_graph_max_count(void)
 577 {
 578         return graph_id;
 579 }
 580
 581 RTE_LOG_REGISTER_DEFAULT(rte_graph_logtype, INFO);