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); 582