tree.c (16712B)
1 /* 2 * 3 * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 4 * 5 * Copyright 2007-2019 Broadcom Inc. All rights reserved. 6 * 7 * File: tree.c 8 * Purpose: board tree based programming 9 */ 10 11 12 #include <shared/bsl.h> 13 14 #include <sal/core/alloc.h> 15 #include <sal/core/libc.h> 16 #include <bcm/error.h> 17 #include <bcm/types.h> 18 #include <bcm/trunk.h> 19 #include <bcm/stack.h> 20 #include <board/board.h> 21 #include <board/manager.h> 22 #include <board_int/support.h> 23 24 25 /* Tree programmer 26 27 Based on a connection list, the Tree Programmer creates a tree of 28 devices, with each device represented by a vertex, and each 29 connection between devices represented by an edge (actually two 30 edges). It then then traverses the tree, calling an 'edge 31 programmer' function for each edge in the tree, and a 'vertex 32 programmer' function for each vertex (more or less). Typically, an 33 edge programmer will create trunks between devices when necessary, 34 and a vertex programmer will program modport mapping. 35 36 This is intended to work for both local board programming and stack 37 board programming. Although the algorithm is the same, programming 38 requirements are somewhat different between the local and stack 39 case, so the API programming is abstracted out of this function. 40 The only BCM API this subsystem calls is bcm_unit_local(). 41 42 Returns BCM_E_CONFIG if the connection list does not constitute a 43 mathematical tree. 44 45 It may be a future enhancement to accept a general graph of devices 46 when a spanning tree or other loop pruning algorithm is introduced. 47 48 Algorithm: 49 50 Each unit is a vertex in a tree. Each connection adds two edges, 51 one for each direction connecting two vertexes. Each edge has 52 vertex endpoints that are either the same as an existing edge, 53 where the edge data populates a trunk, or becomes a new edge of 54 the graph. 55 56 Once all the edges are added, the resulting graph is checked to 57 see if it is a mathematical tree. If it isn't then return 58 failure. Otherwise, traverse all the vertexes in the tree. If 59 the vertex is local, iterate across all edges of the vertex. Call 60 the edge programmer for the edge that was found. Next, traverse 61 the subtree from the destination vertex of the edge, calling the 62 vertex programmer for each vertex in the subtree being traversed, 63 along with the parent vertex of the subtree. 64 65 Add all connections 66 BCM_E_CONFIG if graph is not a tree 67 for each vertex 68 if vertex is local 69 for each edge in vertex 70 program edge 71 traverse_subtree(vertex.destination) { 72 program vertex 73 } 74 end 75 end 76 end 77 78 */ 79 80 struct vertex_s; 81 82 typedef struct edge_s { 83 bcm_gport_t src; /* source port */ 84 bcm_gport_t dst; /* destination port */ 85 struct vertex_s *vertex; /* parent vertex */ 86 bcm_trunk_add_info_t trunk; /* trunk */ 87 struct edge_s *next; /* next edge */ 88 } edge_t; 89 90 typedef struct vertex_s { 91 int unit; /* unit number */ 92 int modid; /* device modid */ 93 int visited; /* visited? for traversals */ 94 edge_t *edge; /* edges */ 95 bcm_trunk_chip_info_t ti; /* trunk info */ 96 } vertex_t; 97 98 typedef struct tree_s { 99 board_tree_driver_t *driver; 100 int num; /* unit number */ 101 vertex_t *vertex; /* vertex, indexed by unit */ 102 } tree_t; 103 104 typedef int (*vertex_cb)(tree_t *tree, vertex_t *vertex, void *user_data); 105 typedef int (*tree_cb)(tree_t *tree, vertex_t *vertex, void *user_data); 106 107 /* return TRUE is the vertex is valid */ 108 #define VERTEX_VALID(v) (((v) != NULL) && ((v)->unit >= 0)) 109 110 /* shorthand because it's used a lot */ 111 #define UNIT BCM_GPORT_DEVPORT_DEVID_GET 112 113 114 #define MAX(a,b) (((a)>(b))?(a):(b)) 115 116 117 /* 118 * Function: 119 * _trunk_add 120 * Purpose: 121 * Add trunk member to edge trunk 122 * Parameters: 123 * e - (INOUT) 124 * member - (IN) 125 * Returns: 126 * BCM_E_NONE - success 127 * BCM_E_XXX - failed 128 */ 129 STATIC int 130 _trunk_add(edge_t *e, bcm_gport_t member) 131 { 132 int rv = BCM_E_FULL; 133 134 if (e->trunk.num_ports < BCM_TRUNK_MAX_PORTCNT) { 135 e->trunk.tp[e->trunk.num_ports] = member; 136 e->trunk.tm[e->trunk.num_ports] = -1; 137 e->trunk.num_ports++; 138 rv = BCM_E_NONE; 139 } 140 141 return rv; 142 } 143 144 145 /* 146 * Function: 147 * _edge_add 148 * Purpose: 149 * Add an edge, identified by [src-dst], where src is a port 150 * associated with the vertex, returning the edge in edgep. 151 * Parameters: 152 * edgep - (OUT) edge output 153 * vertex - (IN) vertex of src 154 * src - (IN) edge src port 155 * dst - (IN) edge dst port 156 * Returns: 157 * BCM_E_NONE - success 158 * BCM_E_XXX - failed 159 */ 160 STATIC int 161 _edge_add(edge_t **edgep, vertex_t *vertex, bcm_gport_t src, bcm_gport_t dst) 162 { 163 int rv; 164 edge_t *edge, *prev; 165 166 edge=*edgep; 167 prev=NULL; 168 for (; edge != NULL; edge=edge->next) { 169 if (edge->src == src) { 170 return BCM_E_CONFIG; 171 } 172 if (UNIT(edge->dst) == UNIT(dst)) { 173 return _trunk_add(edge, src); 174 } 175 prev=edge; 176 } 177 178 /* create a new edge */ 179 edge = ALLOC(sizeof(*edge)); 180 if (edge == NULL) { 181 return BCM_E_MEMORY; 182 } 183 184 edge->src = src; 185 edge->dst = dst; 186 edge->vertex = vertex; 187 bcm_trunk_add_info_t_init(&edge->trunk); 188 edge->next = NULL; 189 rv = _trunk_add(edge, src); 190 if (BCM_SUCCESS(rv)) { 191 if (prev) { 192 /* add to edge list */ 193 prev->next = edge; 194 } else { 195 /* first edge in vertex */ 196 *edgep = edge; 197 } 198 } else { 199 FREE(edge); 200 } 201 202 return rv; 203 } 204 205 /* 206 * Function: 207 * _vertex_add 208 * Purpose: 209 * Add a vertex to a tree, calling out to the info function 210 * Parameters: 211 * t - (IN) tree 212 * vertex - (INOUT) vertex 213 * unit - (IN) unit ID for vertex 214 * Returns: 215 * BCM_E_NONE - success 216 * BCM_E_XXX - failed 217 */ 218 STATIC int 219 _vertex_add(tree_t *t, vertex_t *vertex, int unit) 220 { 221 int rv; 222 223 vertex->unit = unit; 224 vertex->visited = FALSE; 225 vertex->edge = NULL; 226 rv = t->driver->info(unit, &vertex->modid, &vertex->ti, 227 t->driver->user_data); 228 229 return rv; 230 } 231 232 /* 233 * Function: 234 * _connection_add 235 * Purpose: 236 * Add the given simplex connection to the tree 237 * Parameters: 238 * t - (IN) tree 239 * src - (IN) connection src port 240 * dst - (IN) connection dst port 241 * Returns: 242 * BCM_E_NONE - success 243 * BCM_E_XXX - failed 244 */ 245 STATIC int 246 _connection_add(tree_t *t, bcm_gport_t src, bcm_gport_t dst) 247 { 248 int src_u, rv; 249 vertex_t *vertex; 250 251 src_u = UNIT(src); 252 vertex = &t->vertex[src_u]; 253 rv = BCM_E_NONE; 254 if (!VERTEX_VALID(vertex)) { 255 rv = _vertex_add(t, vertex, src_u); 256 if (t->num < src_u) { 257 t->num = src_u+1; 258 } 259 } 260 261 if (BCM_SUCCESS(rv)) { 262 rv = _edge_add(&vertex->edge, vertex, src, dst); 263 } 264 265 266 return rv; 267 268 } 269 270 /* 271 * Function: 272 * _visit 273 * Purpose: 274 * Visit each vertex of the tree that has not already been visited 275 * breadth first starting with the given vertex 276 * Parameters: 277 * t - (IN) tree 278 * v - (IN) starting vertex 279 * cb - (IN) vertex callback 280 * user_data - (IN) 281 * Returns: 282 * BCM_E_NONE - success 283 * BCM_E_XXX - failed 284 */ 285 STATIC int 286 _visit(tree_t *t, vertex_t *v, vertex_cb cb, void *user_data) 287 { 288 edge_t *edge; 289 int vtid; 290 291 v->visited = TRUE; 292 BCM_IF_ERROR_RETURN(cb(t,v,user_data)); 293 for (edge = v->edge; edge != NULL; edge=edge->next) { 294 vtid = UNIT(edge->dst); 295 if (!t->vertex[vtid].visited) { 296 BCM_IF_ERROR_RETURN(_visit(t,&t->vertex[vtid],cb,user_data)); 297 } 298 } 299 300 return BCM_E_NONE; 301 } 302 303 /* 304 * Function: 305 * _reset_visited 306 * Purpose: 307 * Reset all visited flags in the tree 308 * Parameters: 309 * t - (IN) tree 310 * Returns: 311 * BCM_E_NONE - success 312 * BCM_E_XXX - failed 313 */ 314 STATIC void 315 _reset_visited(tree_t *t) 316 { 317 int i; 318 319 for (i=0; i<t->num; i++) { 320 t->vertex[i].visited = FALSE; 321 } 322 } 323 324 /* 325 * Function: 326 * _traverse_subtree_from 327 * Purpose: 328 * Traverse the subtree rooted at 'from', avoiding traversals 329 * though vertex 'parent'. 330 * Parameters: 331 * t - (IN) tree 332 * parent - (IN) subtree parent 333 * from - (IN) subtree root 334 * cb - (IN) vertex callback 335 * user_data - (IN) vertex data 336 * Returns: 337 * BCM_E_NONE - success 338 * BCM_E_XXX - failed 339 */ 340 STATIC int 341 _traverse_subtree_from(tree_t *t, vertex_t *parent, vertex_t *from, 342 vertex_cb cb, void *user_data) 343 { 344 _reset_visited(t); 345 if (parent) { 346 parent->visited = TRUE; 347 } 348 return _visit(t, from, cb, user_data); 349 } 350 351 /* 352 * Function: 353 * _count_edges 354 * Purpose: 355 * Returns the number of directed edges in the tree 356 * Parameters: 357 * t - (IN) tree 358 * Returns: 359 * number of directed edges 360 */ 361 STATIC int 362 _count_edges(tree_t *t) 363 { 364 int edge_count, i; 365 edge_t *edge; 366 vertex_t *vertex; 367 368 /* Count the number of edges */ 369 edge_count = 0; 370 for (i=0; i<t->num; i++) { 371 vertex = &t->vertex[i]; 372 if (!VERTEX_VALID(vertex)) { 373 continue; 374 } 375 for (edge = vertex->edge; edge != NULL; edge=edge->next) { 376 edge_count++; 377 } 378 } 379 380 return edge_count; 381 } 382 383 /* 384 * Function: 385 * _tree_p 386 * Purpose: 387 * Return TRUE if the given graph if a mathematical tree 388 * Parameters: 389 * t - (IN) tree 390 * Returns: 391 * boolean 392 */ 393 STATIC int 394 _tree_p(tree_t *t) 395 { 396 int edge_count; 397 398 /* Count the number of edges */ 399 edge_count = _count_edges(t); 400 401 /* Must have an even number of directed edges, and the number of 402 undirected edges must be one greater than the numver of 403 verticies */ 404 return (((edge_count & 1) == 0) && (((edge_count/2)+1) == t->num)); 405 } 406 407 /* 408 * Function: 409 * _tree_connection_add 410 * Purpose: 411 * Add duplex connection to tree as two simplex edges 412 * Parameters: 413 * t - (IN) tree 414 * connection - (IN) connection 415 * Returns: 416 */ 417 STATIC int 418 _tree_connection_add(tree_t *t, board_connection_t *connection) 419 { 420 BCM_IF_ERROR_RETURN(_connection_add(t, connection->from, connection->to)); 421 BCM_IF_ERROR_RETURN(_connection_add(t, connection->to, connection->from)); 422 423 return BCM_E_NONE; 424 } 425 426 /* 427 * Function: 428 * _tree_init 429 * Purpose: 430 * Initialize tree 431 * Parameters: 432 * t - (IN) tree 433 * driver - (IN) tree driver 434 * Returns: 435 * TRUE - tree was created 436 * BCM_E_NONE - connection does not represent a tree 437 * BCM_E_XXX - failed 438 */ 439 STATIC int 440 _tree_init(tree_t *t, board_tree_driver_t *driver) 441 { 442 int i, internal, size; 443 444 /* See if there's anything to connect, and calculate the size of 445 the vertex array. */ 446 internal=0; 447 for (i=0; i<driver->num_connection; i++) { 448 if (driver->connection[i].from != BCM_GPORT_TYPE_NONE && 449 driver->connection[i].to != BCM_GPORT_TYPE_NONE) { 450 internal = MAX(internal,UNIT(driver->connection[i].from)+1); 451 internal = MAX(internal,UNIT(driver->connection[i].to)+1); 452 } 453 } 454 455 if (internal == 0) { 456 /* Nothing to connect */ 457 return BCM_E_EMPTY; 458 } 459 460 sal_memset(t, 0, sizeof(*t)); 461 t->driver = driver; 462 463 size = internal * sizeof(vertex_t); 464 t->vertex = ALLOC(size); 465 if (t->vertex == NULL) { 466 return BCM_E_MEMORY; 467 } 468 sal_memset(t->vertex, 0, size); 469 470 471 /* Mark all vertexes invalid */ 472 for (i=0; i<internal; i++) { 473 t->vertex[i].unit=-1; 474 } 475 476 /* Add connections */ 477 for (i=0; i<driver->num_connection; i++) { 478 if ((driver->connection[i].from != BCM_GPORT_TYPE_NONE) && 479 (driver->connection[i].to != BCM_GPORT_TYPE_NONE)) { 480 _tree_connection_add(t, &driver->connection[i]); 481 } 482 } 483 484 return _tree_p(t); 485 } 486 487 /* 488 * Function: 489 * _tree_free 490 * Purpose: 491 * Free allocated memory from tree 492 * Parameters: 493 * t - (IN) tree 494 * Returns: 495 * void 496 */ 497 STATIC void 498 _tree_free(tree_t *t) 499 { 500 int i; 501 edge_t *edge, *next; 502 vertex_t *vertex; 503 504 for (i=0; i<t->num; i++) { 505 vertex = &t->vertex[i]; 506 if (!VERTEX_VALID(vertex)) { 507 continue; 508 } 509 510 for (edge = vertex->edge; edge != NULL; edge=next) { 511 next=edge->next; 512 FREE(edge); 513 } 514 } 515 FREE(t->vertex); 516 } 517 518 /* 519 * Function: 520 * _program_edge 521 * Purpose: 522 * Call edge programmer for given vertex and edge 523 * Parameters: 524 * t - (IN) tree 525 * vertex - (IN) vertex 526 * edge - (IN) edge 527 * Returns: 528 */ 529 STATIC int 530 _program_edge(tree_t *t, vertex_t *vertex, edge_t *edge) 531 { 532 return t->driver->edge(vertex->unit, &vertex->ti, 533 &edge->trunk, t->driver->user_data); 534 } 535 536 /* 537 * Function: 538 * _program_vertex 539 * Purpose: 540 * Call vertex programmer for given vertex 541 * Parameters: 542 * t - (IN) tree 543 * vertex - (IN) vertex 544 * user_data - (IN) vertex callback user data 545 * Returns: 546 * BCM_E_NONE - success 547 * BCM_E_XXX - failed 548 */ 549 STATIC int 550 _program_vertex(tree_t *t, vertex_t *dst, void *user_data) 551 { 552 edge_t *edge = (edge_t *)user_data; 553 vertex_t *src = edge->vertex; 554 555 return t->driver->vertex(src->unit, dst->modid, edge->src, 556 t->driver->user_data); 557 } 558 559 /* 560 * Function: 561 * _board_connect_vertex 562 * Purpose: 563 * Tree programmer tree traversal callback 564 * Parameters: 565 * t - (IN) tree 566 * vertex - (IN) vertex 567 * user_data - (IN) vertex callback user data 568 * Returns: 569 * BCM_E_NONE - success 570 * BCM_E_XXX - failed 571 */ 572 STATIC int 573 _board_connect_vertex(tree_t *t, vertex_t *vertex, void *user_data) 574 { 575 int rv = BCM_E_INTERNAL; /* It's expected that there's at least 576 one edge per vertex. */ 577 edge_t *edge; 578 vertex_t *to; 579 580 581 /* Cannot use bcm_unit_remote, because the unit numbers will not 582 likely be attached for slave systems, and bcm_unit_remote will 583 return false. */ 584 if (!bcm_unit_local(vertex->unit)) { 585 LOG_VERBOSE(BSL_LS_BOARD_COMMON, 586 (BSL_META("Board programming for remote unit %d not required.\n"), 587 vertex->unit)); 588 return BCM_E_NONE; 589 } 590 591 LOG_VERBOSE(BSL_LS_BOARD_COMMON, 592 (BSL_META("Board programming unit %d\n"), 593 vertex->unit)); 594 for (edge = vertex->edge; edge != NULL; edge = edge->next) { 595 596 /* only local units require edge programming */ 597 rv = _program_edge(t, vertex, edge); 598 if (BCM_FAILURE(rv)) { 599 break; 600 } 601 602 to = &t->vertex[UNIT(edge->dst)]; 603 rv = _traverse_subtree_from(t, vertex, to, 604 _program_vertex, (void *)edge); 605 if (BCM_FAILURE(rv)) { 606 break; 607 } 608 } 609 610 if (BCM_FAILURE(rv)) { 611 LOG_VERBOSE(BSL_LS_BOARD_COMMON, 612 (BSL_META("Board programming unit %d failed (%d)\n"), 613 vertex->unit, rv)); 614 } 615 return rv; 616 } 617 618 /* 619 * Function: 620 * _tree_traverse 621 * Purpose: 622 * Breadth first tree traversal 623 * Parameters: 624 * t - (IN) tree 625 * cb - (IN) vertex callback 626 * user_data - (IN) callback user data 627 * Returns: 628 * BCM_E_NONE - success 629 * BCM_E_XXX - failed 630 */ 631 STATIC int 632 _tree_traverse(tree_t *tree, tree_cb cb, void *user_data) 633 { 634 int i,rv; 635 vertex_t *vertex; 636 637 rv = BCM_E_NONE; 638 639 for (i=0; i<tree->num; i++) { 640 vertex = &tree->vertex[i]; 641 if (!VERTEX_VALID(vertex)) { 642 continue; 643 } 644 rv = cb(tree, vertex, user_data); 645 if (BCM_FAILURE(rv)) { 646 break; 647 } 648 } 649 650 return rv; 651 } 652 653 /* 654 * Function: 655 * board_tree_connect 656 * Purpose: 657 * Tree based board connection algorithm 658 * Parameters: 659 * tree_driver - (IN) connection algorithm 660 * Returns: 661 * BCM_E_NONE - success 662 * BCM_E_XXX - failed 663 */ 664 int 665 board_tree_connect(board_tree_driver_t *tree_driver) 666 { 667 int rv; 668 tree_t tree; 669 670 rv = _tree_init(&tree, tree_driver); 671 if (BCM_SUCCESS(rv)) { 672 _tree_traverse(&tree, _board_connect_vertex, NULL); 673 _tree_free(&tree); 674 } else if (rv == BCM_E_EMPTY) { 675 /* Nothing in the tree, so there's nothing to do */ 676 rv = BCM_E_NONE; 677 } 678 679 return rv; 680 }