topology.c (31671B)
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: topology.c 8 * Purpose: Sample topology analysis implementation 9 * Requires: 10 * Notes: 11 * Although this is set up to generate data on a db_ref object, 12 * this code is not re-entrant and care should be taken to ensure 13 * that topology create is not called multiple times simultaneously. 14 */ 15 16 #include <shared/bsl.h> 17 18 #include <bcm/error.h> 19 20 #include <appl/stktask/topology.h> 21 #include <appl/stktask/topo_brd.h> 22 #include <appl/stktask/stktask.h> 23 #include <appl/cpudb/cpudb.h> 24 25 #include <sal/core/libc.h> 26 #include <shared/alloc.h> 27 28 #include "topo_int.h" 29 30 typedef uint32 weight_t; 31 32 /* Synchronize access to topo structures */ 33 #define TOPO_LOCK_INIT if (topo_lock == NULL) topo_lock_init() 34 #define TOPO_LOCK_CHECK if (topo_lock == NULL) return BCM_E_MEMORY 35 #define TOPO_LOCK sal_mutex_take(topo_lock, sal_sem_FOREVER) 36 #define TOPO_UNLOCK sal_mutex_give(topo_lock) 37 38 STATIC void _topology_destroy(cpudb_ref_t db_ref); 39 40 static sal_mutex_t topo_lock; 41 static uint32 topo_rsvd_modid = 0; 42 static topology_mod_id_assign_f topology_mod_id_assign_func = NULL; 43 44 STATIC void 45 topo_lock_init(void) 46 { 47 if (topo_lock == NULL) { 48 topo_lock = sal_mutex_create("topo_lock"); 49 } 50 if (topo_lock == NULL) { 51 LOG_ERROR(BSL_LS_TKS_TOPOLOGY, 52 (BSL_META("TOPO: Could not create topology mutex\n"))); 53 } 54 } 55 56 57 /* Boolean: Is connection matrix complete? */ 58 59 STATIC int 60 tp_all_destinations_reachable(cpudb_ref_t db_ref) 61 { 62 int i, j; 63 64 for (i = 0; i < db_ref->num_cpus; i++) { 65 for (j = 0; j < db_ref->num_cpus; j++) { 66 if (i == j) { 67 continue; 68 } 69 if (!TP_REACHABLE(db_ref, i, j)) { 70 return FALSE; 71 } 72 } 73 } 74 75 return TRUE; 76 } 77 78 /* Set up internal indexes for CPUs */ 79 80 STATIC void 81 tp_index_init(cpudb_ref_t db_ref) 82 { 83 cpudb_entry_t *entry; 84 int entry_count = 0; 85 86 CPUDB_FOREACH_ENTRY(db_ref, entry) { 87 entry->topo_idx = entry_count++; 88 } 89 90 #if defined(BROADCOM_DEBUG) 91 if (entry_count != db_ref->num_cpus) { 92 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 93 (BSL_META("TOPO WARNING: Bad cpu count: db %d. local %d\n"), 94 db_ref->num_cpus, entry_count)); 95 } 96 #endif /* BROADCOM_DEBUG */ 97 } 98 99 /* 100 * Originally, did depth first search. This has been replaced, 101 * but the new code may be overridden by defining TOPO_NO_SHORTEST_PATH. 102 * This will likely go away soon. 103 */ 104 #ifndef TOPO_NO_SHORTEST_PATH 105 106 /* 107 * SHORTEST HOP TOPOLOGY 108 * 109 * 1. Initialize weights for processing. Assume the DB has TX/RX connections 110 * completed. Set first found connection to immediate neighbors. Fabric 111 * trunking takes care of redundant links. 112 * 113 * 2. Iteratively process next possible hops until no more edges are added. 114 */ 115 #define TP_WEIGHT(_w, _s, _d) (_w)[((_s)*CPUDB_CPU_MAX)+(_d)] 116 117 STATIC void 118 tp_weights_init(cpudb_ref_t db_ref, weight_t *weights) 119 { 120 int s_idx, d_idx; 121 cpudb_entry_t *src_entry, *dest_entry; 122 int i; 123 124 125 CPUDB_FOREACH_ENTRY(db_ref, src_entry) { 126 s_idx = src_entry->topo_idx; 127 for (i = 0; i < src_entry->base.num_stk_ports; i++) { 128 cpudb_unit_port_t *sp_base = &src_entry->base.stk_ports[i]; 129 cpudb_stk_port_t *sp = &src_entry->sp_info[i]; 130 if (sp->flags == 0) { /* no info on port */ 131 continue; 132 } 133 if (sp->flags & ( 134 CPUDB_SPF_TX_DISABLE_FORCE | /* disabled */ 135 CPUDB_SPF_NO_LINK | /* no link on port */ 136 CPUDB_SPF_INACTIVE | /* no pkts on port */ 137 CPUDB_SPF_ETHERNET )) { /* Ethernet port */ 138 continue; 139 } 140 /* If cut ports are disabled, skip */ 141 if ((sp->flags & CPUDB_SPF_CUT_PORT) && 142 (sp_base->bflags & CPUDB_UPF_DISABLE_IF_CUT)) { 143 /* This pops up with redundant SL stack links */ 144 LOG_VERBOSE(BSL_LS_TKS_TOPOLOGY, 145 (BSL_META("skipping cut ports with flag\n"))); 146 continue; 147 } 148 CPUDB_KEY_SEARCH(db_ref, sp->tx_cpu_key, dest_entry); 149 if (dest_entry == NULL) { 150 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 151 (BSL_META("TOPO WARNING: Could not find tx key " 152 CPUDB_KEY_FMT_EOLN), 153 CPUDB_KEY_DISP(sp->tx_cpu_key))); 154 continue; 155 } 156 d_idx = dest_entry->topo_idx; 157 if (TP_REACHABLE(db_ref, s_idx, d_idx)) { 158 /* 159 * Already have a connection indicated; 160 * fabric trunking handles this case 161 */ 162 continue; 163 } 164 165 TP_WEIGHT(weights, s_idx, d_idx) = TOPO_DEFAULT_WEIGHT; 166 /* Below indicates is reachable and by what stk port */ 167 TP_TX_CXN(db_ref, s_idx, d_idx) = i; 168 TP_RX_CXN(db_ref, d_idx, s_idx) = sp->tx_stk_idx; 169 /* Check for duplex connection and set up if so. */ 170 if (sp->flags & CPUDB_SPF_DUPLEX) { 171 if (!TP_REACHABLE(db_ref, d_idx, s_idx)) { 172 TP_WEIGHT(weights, d_idx, s_idx) = TOPO_DEFAULT_WEIGHT; 173 /* Below indicates is reachable and by what stk port */ 174 TP_TX_CXN(db_ref, d_idx, s_idx) = sp->tx_stk_idx; 175 TP_RX_CXN(db_ref, s_idx, d_idx) = i; 176 } else { 177 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 178 (BSL_META("TOPO WARNING: Duplex port already marked, " 179 "src (%d,%d), dest (%d,%d)\n"), s_idx, i, 180 d_idx, sp->tx_stk_idx)); 181 } 182 } 183 } 184 } 185 } 186 187 /* Return TRUE if the cpudb is all full duplex */ 188 STATIC int 189 tp_full_duplex(cpudb_ref_t db_ref) 190 { 191 cpudb_entry_t *entry; 192 int i; 193 194 CPUDB_FOREACH_ENTRY(db_ref, entry) { 195 for (i = 0; i < entry->base.num_stk_ports; i++) { 196 cpudb_stk_port_t *sp = &entry->sp_info[i]; 197 if (sp->flags == 0) { /* no info on port */ 198 continue; 199 } 200 if (sp->flags & (CPUDB_SPF_TX_DISABLE_FORCE | /* disabled */ 201 CPUDB_SPF_NO_LINK | /* no link on port */ 202 CPUDB_SPF_INACTIVE | /* no pkts on port */ 203 CPUDB_SPF_ETHERNET )) { /* Ethernet port */ 204 continue; 205 } 206 if (!(sp->flags & CPUDB_SPF_DUPLEX)) { 207 return FALSE; 208 } 209 } 210 } 211 212 return TRUE; 213 } 214 215 /* 216 * Run through src->mid connections; then mid->dest connections. If 217 * src->dest is not known, add it with weighted sum via src->mid->dest. 218 * 219 * Note that we don't actually need to look at weights since we're 220 * doing a breadth first search and all initial weights are 1. But 221 * I'll leave it here in case there's a need for assigning different 222 * weights to different (types of) links. 223 * 224 * If all the connections are full duplex, make the reverse path the 225 * same as the forward path. 226 */ 227 228 229 230 STATIC void 231 tp_weights_process(cpudb_ref_t db_ref, weight_t *weights) 232 { 233 int count; 234 int src_idx, mid_idx, dest_idx; 235 int full_duplex; 236 237 full_duplex = tp_full_duplex(db_ref); 238 239 do { 240 count = 0; 241 for (src_idx = 0; src_idx < db_ref->num_cpus; src_idx++) { 242 for (mid_idx = 0; mid_idx < db_ref->num_cpus; mid_idx++) { 243 if (mid_idx == src_idx || 244 !TP_REACHABLE(db_ref, src_idx, mid_idx)) { 245 continue; 246 } 247 for (dest_idx = 0; dest_idx < db_ref->num_cpus; dest_idx++) { 248 if (dest_idx == src_idx || dest_idx == mid_idx) { 249 continue; 250 } 251 if (!TP_REACHABLE(db_ref, mid_idx, dest_idx)) { 252 continue; 253 } 254 if (!TP_REACHABLE(db_ref, src_idx, dest_idx) || 255 (TP_WEIGHT(weights, src_idx, mid_idx) + 256 TP_WEIGHT(weights, mid_idx, dest_idx) < 257 TP_WEIGHT(weights, src_idx, dest_idx))) { 258 int tx,rx,w; 259 ++count; 260 TP_TX_CXN(db_ref, src_idx, dest_idx) = 261 (tx=TP_TX_CXN(db_ref, src_idx, mid_idx)); 262 TP_RX_CXN(db_ref, dest_idx, src_idx) = 263 (rx=TP_RX_CXN(db_ref, dest_idx, mid_idx)); 264 TP_WEIGHT(weights, src_idx, dest_idx) = 265 (w=(TP_WEIGHT(weights, src_idx, mid_idx) + 266 TP_WEIGHT(weights, mid_idx, dest_idx))); 267 if (full_duplex) { 268 TP_TX_CXN(db_ref, dest_idx, src_idx) = rx; 269 TP_RX_CXN(db_ref, src_idx, dest_idx) = tx; 270 TP_WEIGHT(weights, dest_idx, src_idx) = w; 271 } 272 } 273 } 274 } 275 } 276 } while (count > 0); 277 } 278 279 280 /* 281 * find the paths from each cpu to every other cpu 282 * (shortest path version) 283 */ 284 STATIC int 285 tp_find_paths(cpudb_ref_t db_ref) 286 { 287 weight_t *weights; 288 int size; 289 290 size = CPUDB_CPU_MAX * CPUDB_CPU_MAX * sizeof(*weights); 291 weights = sal_alloc(size, "topo_weights"); 292 if (weights == NULL) { 293 return BCM_E_MEMORY; 294 } 295 sal_memset(weights, 0, size); 296 tp_weights_init(db_ref, weights); 297 tp_weights_process(db_ref, weights); 298 sal_free(weights); 299 return BCM_E_NONE; 300 } 301 302 #else /* TOPO_NO_SHORTEST_PATH */ 303 304 /* 305 * Old, depth first search path processing. 306 */ 307 308 /* 309 * The connection src->dest has just been added. Look for 310 * connections src->dest->new_dest where src->new_dest doesn't exist yet. 311 * 312 * Returns number of cxns added. 313 * 314 * The RX information is updated as well. The RX port at new for (src->new) 315 * is the same as the RX port at new for (dest->new). 316 */ 317 318 STATIC int 319 tp_one_cxn_update(cpudb_ref_t db_ref, int src_idx, int dest_idx) 320 { 321 int new_dest; 322 int cxns_added = 0; 323 324 for (new_dest = 0; new_dest < db_ref->num_cpus; new_dest++) { 325 if (new_dest == dest_idx || new_dest == src_idx) { 326 continue; 327 } 328 if (TP_REACHABLE(db_ref, dest_idx, new_dest) && 329 !TP_REACHABLE(db_ref, src_idx, new_dest)) { 330 TP_TX_CXN(db_ref, src_idx, new_dest) = 331 TP_TX_CXN(db_ref, src_idx, dest_idx); 332 TP_RX_CXN(db_ref, new_dest, src_idx) = 333 TP_RX_CXN(db_ref, new_dest, dest_idx); 334 cxns_added++; 335 } 336 } 337 338 return cxns_added; 339 } 340 341 342 /* 343 * Update the connection matrix after an edge has been added. 344 * 345 * Given a set of CPUs that have new destinations. Look for new 346 * CPUs that can reach anything in this set, and add any new edges 347 * found. 348 * 349 * When a connection src->dest is added, we need to keep track of 350 * src (gets placed on new_cpus). Then, do a recursive call to 351 * look for deeper connections. 352 * 353 * The worst case depth of this is CPUDB_CPU_MAX - 1. 354 */ 355 356 STATIC void 357 tp_cxns_update(cpudb_ref_t db_ref, 358 uint8 *cpu_list, 359 int cpu_count) 360 { 361 uint8 new_cpus[CPUDB_CPU_MAX]; 362 int new_count = 0; 363 uint8 src_idx; 364 uint8 mid_cpu; 365 int i; 366 367 #if defined(BROADCOM_DEBUG) 368 static volatile int depth = 0; 369 370 if (depth++ > CPUDB_CPU_MAX) { 371 TOPO_ERR(("TOPO ERROR: cxn update depth too great\n")); 372 return; 373 } 374 #endif /* BROADCOM_DEBUG */ 375 376 /* 377 * Look for new connections: new_idx->mid_cpu->dest_idx where 378 * new->dest_idx is NOT yet defined; mid_cpu comes from cpu_list. 379 */ 380 381 for (i = 0; i < cpu_count; i++) { 382 mid_cpu = cpu_list[i]; 383 for (src_idx = 0; src_idx < db_ref->num_cpus; src_idx++) { 384 if (src_idx == mid_cpu) { 385 continue; 386 } 387 if (TP_REACHABLE(db_ref, src_idx, mid_cpu)) { 388 if (tp_one_cxn_update(db_ref, src_idx, mid_cpu) > 0) { 389 /* Added connections; need to go deeper */ 390 new_cpus[new_count++] = src_idx; 391 } 392 } 393 } 394 } 395 396 if (new_count > 0) { /* Recursive call to handle new connections */ 397 tp_cxns_update(db_ref, new_cpus, new_count); 398 } 399 400 #if defined(BROADCOM_DEBUG) 401 depth--; 402 #endif /* BROADCOM_DEBUG */ 403 } 404 405 /* 406 * Add the edge from src_idx to dest_idx using cxn stk_idx and update 407 * all connections 408 */ 409 410 STATIC void 411 tp_edge_add(cpudb_ref_t db_ref, int src_idx, int dest_idx, 412 int src_stk_idx, int dest_stk_idx) 413 { 414 uint8 src_idx8; 415 416 TP_TX_CXN(db_ref, src_idx, dest_idx) = src_stk_idx; 417 TP_RX_CXN(db_ref, dest_idx, src_idx) = dest_stk_idx; 418 tp_one_cxn_update(db_ref, src_idx, dest_idx); 419 420 src_idx8 = src_idx; 421 tp_cxns_update(db_ref, &src_idx8, 1); 422 } 423 424 /* Process all edges that are forced enabled */ 425 STATIC int 426 tp_forced_up(cpudb_ref_t db_ref) 427 { 428 int i; 429 int src_idx, dest_idx; /* CPUs */ 430 cpudb_entry_t *src_entry, *dest_entry; 431 cpudb_stk_port_t *sp; 432 433 CPUDB_FOREACH_ENTRY(db_ref, src_entry) { 434 src_idx = src_entry->topo_idx; 435 if (src_idx < 0) { 436 LOG_ERROR(BSL_LS_TKS_TOPOLOGY, 437 (BSL_META("TOPO ERROR: Could not find src key " 438 CPUDB_KEY_FMT_EOLN), 439 CPUDB_KEY_DISP(src_entry->base.key))); 440 return BCM_E_FAIL; 441 } 442 443 for (i = 0; i < src_entry->base.num_stk_ports; i++) { 444 sp = &src_entry->sp_info[i]; 445 if (sp->flags & CPUDB_SPF_INACTIVE) { 446 continue; 447 } 448 if (sp->flags & CPUDB_SPF_TX_ENABLED) { /* Forced enabled */ 449 CPUDB_KEY_SEARCH(db_ref, sp->tx_cpu_key, dest_entry); 450 if (dest_entry == NULL) { 451 LOG_ERROR(BSL_LS_TKS_TOPOLOGY, 452 (BSL_META("TOPO ERROR: Could not find dest key " 453 CPUDB_KEY_FMT_EOLN), 454 CPUDB_KEY_DISP(sp->tx_cpu_key))); 455 return BCM_E_FAIL; 456 } 457 458 dest_idx = dest_entry->topo_idx; 459 if (TP_REACHABLE(db_ref, src_idx, dest_idx)) { 460 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 461 (BSL_META("TOPO WARNING: " 462 "Multiple paths in pre-enabled links: " 463 CPUDB_KEY_FMT " to " CPUDB_KEY_FMT_EOLN), 464 CPUDB_KEY_DISP(src_entry->base.key), 465 CPUDB_KEY_DISP(sp->tx_cpu_key))); 466 } 467 tp_edge_add(db_ref, src_idx, dest_idx, i, sp->tx_stk_idx); 468 } 469 } 470 } 471 472 return BCM_E_NONE; 473 } 474 475 /* Process all edges that are neither already enabled, nor forced disabled. */ 476 477 STATIC void 478 tp_process_edges(cpudb_ref_t db_ref) 479 { 480 int i; 481 int src_idx, dest_idx; /* CPUs */ 482 cpudb_entry_t *src_entry, *dest_entry; 483 cpudb_stk_port_t *sp; 484 485 /* Now process all remaining edges */ 486 CPUDB_FOREACH_ENTRY(db_ref, src_entry) { 487 src_idx = src_entry->topo_idx; 488 for (i = 0; i < src_entry->base.num_stk_ports; i++) { 489 sp = &src_entry->sp_info[i]; 490 if (sp->flags == 0) { /* no info on port */ 491 continue; 492 } 493 if (sp->flags & ( 494 CPUDB_SPF_TX_ENABLED | /* Already enabled */ 495 CPUDB_SPF_TX_DISABLE_FORCE | /* disabled */ 496 CPUDB_SPF_NO_LINK | /* no link on port */ 497 CPUDB_SPF_INACTIVE | /* no pkts on port */ 498 CPUDB_SPF_ETHERNET) ) { /* Ethernet port */ 499 continue; 500 } 501 CPUDB_KEY_SEARCH(db_ref, sp->tx_cpu_key, dest_entry); 502 if (dest_entry == NULL) { 503 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 504 (BSL_META("TOPO WARNING: Could not find tx key " 505 CPUDB_KEY_FMT_EOLN), 506 CPUDB_KEY_DISP(sp->tx_cpu_key))); 507 continue; 508 } 509 dest_idx = dest_entry->topo_idx; 510 if (!TP_REACHABLE(db_ref, src_idx, dest_idx)) { /* Add the edge */ 511 sp->flags |= CPUDB_SPF_TX_ENABLED; 512 tp_edge_add(db_ref, src_idx, dest_idx, i, sp->tx_stk_idx); 513 } 514 } 515 } 516 } 517 518 /* 519 * find the paths from each cpu to every other cpu 520 * (first path version) 521 */ 522 STATIC int 523 tp_find_paths(cpudb_ref_t db_ref) 524 { 525 int rv; 526 527 rv = tp_forced_up(db_ref); 528 if (rv < 0) { 529 return rv; 530 } 531 tp_process_edges(db_ref); 532 return BCM_E_NONE; 533 } 534 535 #endif /* !TOPO_NO_SHORTEST_PATH */ 536 537 /* 538 * CUT PORTS: Identify edges not in a spanning tree. 539 * 540 * In SL stacked systems, we have the ability to block broadcast, 541 * multicast and DLF traffic (collectively BC/MC) on a per-port 542 * basis. This is used to handle the case of BC/MC traffic in 543 * duplex rings where infinite loops will occur if all ports are 544 * enabled. In such rings, a "break point" is determined, 545 * and at that CPU, a port in the ring is specified as a "cut" 546 * port. All BC/MC traffic from a cut port is discarded and 547 * no BC/MC traffic should egress on the cut port. 548 * 549 * In fact, both ends of the connection can be marked as cut 550 * ports saving some bandwidth. 551 * 552 * This approach supports rings, stars, interconnected rings and 553 * even rings of rings. Note that unicast traffic can still go 554 * on a shortest path route (so long as the HW supports blocking 555 * BC/MC separately from unicast). 556 * 557 * Determining cut ports is actually very easy: Generate a spanning 558 * tree of the graph (by doing a depth first traversal). The 559 * stack ports on edges not in the spanning tree are cut ports. 560 * 561 * This routine assumes that basic connectivity is okay (all boxes 562 * reachable). It only supports all links being duplex, ignoring 563 * simplex links. It will work for some configurations that 564 * mix simplex and duplex links. (Identify simplex rings to 565 * a vertex leaving a graph with duplex edges; that graph 566 * must be connected.) 567 */ 568 569 /* Use the reserved TOPO1 flags in the CPU DB */ 570 #define CPU_VISITED(entry) ((entry)->flags & CPUDB_F_TOPO1) 571 #define CPU_VISITED_SET(entry) ((entry)->flags |= CPUDB_F_TOPO1) 572 #define CPU_NOT_VISITED_SET(entry) ((entry)->flags &= ~CPUDB_F_TOPO1) 573 574 /* 575 * Start by assuming all edges are out of the tree (CUT flag is 576 * set). Clear cut flag (at both ends) when an edge is added. 577 * Once spanning tree is complete, it's all done (the cut ports 578 * are appropriately marked). 579 * 580 * Given this logic, it's a little easier to talk about UNUSED edges. 581 */ 582 583 #define EDGE_NOT_USED(sp) ((sp)->flags & CPUDB_SPF_CUT_PORT) 584 #define EDGE_NOT_USED_SET(sp) ((sp)->flags |= CPUDB_SPF_CUT_PORT) 585 #define EDGE_USED_SET(sp) ((sp)->flags &= ~CPUDB_SPF_CUT_PORT) 586 587 /* Depth first traversal */ 588 589 STATIC int 590 depth_first(cpudb_ref_t db_ref, cpudb_entry_t *entry) 591 { 592 cpudb_entry_t *other_end; 593 cpudb_stk_port_t *sp, *sp_other_end; 594 int i; 595 596 CPU_VISITED_SET(entry); 597 598 for (i = 0; i < entry->base.num_stk_ports; i++) { 599 sp = &entry->sp_info[i]; 600 601 /* Only pay attention to full duplex ports */ 602 if (!(sp->flags & CPUDB_SPF_DUPLEX)) { 603 continue; 604 } 605 606 if (EDGE_NOT_USED(sp)) { 607 CPUDB_KEY_SEARCH(db_ref, sp->tx_cpu_key, other_end); 608 if (other_end == NULL) { 609 LOG_ERROR(BSL_LS_TKS_TOPOLOGY, 610 (BSL_META("TOPO ERROR: Could not find TX key " 611 CPUDB_KEY_FMT_EOLN), 612 CPUDB_KEY_DISP(sp->tx_cpu_key))); 613 return -1; 614 } 615 if (!(CPU_VISITED(other_end))) { 616 /* Mark both ends of edge as used */ 617 sp_other_end = &(other_end->sp_info[sp->tx_stk_idx]); 618 EDGE_USED_SET(sp); 619 EDGE_USED_SET(sp_other_end); 620 621 /* Recursive search */ 622 depth_first(db_ref, other_end); 623 } 624 } 625 } 626 627 return 0; 628 } 629 630 STATIC int 631 tp_find_cut_ports(cpudb_ref_t db_ref) 632 { 633 cpudb_entry_t *entry; 634 int i; 635 cpudb_stk_port_t *sp; 636 637 /* Clear visited and edge use flags */ 638 CPUDB_FOREACH_ENTRY(db_ref, entry) { 639 CPU_NOT_VISITED_SET(entry); 640 for (i = 0; i < entry->base.num_stk_ports; i++) { 641 sp = &(entry->sp_info[i]); 642 if (sp->flags & CPUDB_SPF_DUPLEX) { 643 EDGE_NOT_USED_SET(sp); 644 } else { /* All simplex edges should be marked used (not cut) */ 645 EDGE_USED_SET(sp); 646 } 647 } 648 } 649 650 /* Start with master entry */ 651 return depth_first(db_ref, db_ref->master_entry); 652 } 653 654 655 /* 656 * Function: 657 * topology_create 658 * Purpose: 659 * Generate the system topology for the given DB 660 * Parameters: 661 * db_ref - DB to update 662 * Returns: 663 * BCM_E_XXX 664 * Notes: 665 * Default behavior is to use shortest path algorithm. Alternative 666 * allows forcing some links up. 667 */ 668 669 int 670 topology_create(cpudb_ref_t db_ref) 671 { 672 int bytes, rv; 673 674 if (db_ref == CPUDB_REF_NULL || db_ref->local_entry == NULL) { 675 return BCM_E_PARAM; 676 } 677 678 TOPO_LOCK_INIT; 679 TOPO_LOCK_CHECK; 680 681 TOPO_LOCK; 682 if (db_ref->topo_cookie != NULL) { 683 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 684 (BSL_META("TOPO WARNING: structure already active\n"))); 685 _topology_destroy(db_ref); 686 } 687 688 db_ref->topo_cookie = sal_alloc(sizeof(topo_info_t), "topo_create"); 689 if (db_ref->topo_cookie == NULL) { 690 TOPO_UNLOCK; 691 return BCM_E_MEMORY; 692 } 693 sal_memset(db_ref->topo_cookie, 0, sizeof(topo_info_t)); 694 695 tp_index_init(db_ref); /* Set up internal CPU indexes */ 696 697 if (db_ref->num_cpus < 2) { /* Only 1 CPU; standalone */ 698 TOPO_UNLOCK; 699 LOG_VERBOSE(BSL_LS_TKS_TOPOLOGY, 700 (BSL_META("TOPO: Single CPU mode\n"))); 701 return BCM_E_NONE; 702 } 703 704 /* Set up topo connection matrices */ 705 bytes = db_ref->num_cpus * db_ref->num_cpus; 706 TP_TX_CXN_MATRIX(db_ref) = sal_alloc(bytes, "topo_tx_matrix"); 707 if (TP_TX_CXN_MATRIX(db_ref) == NULL) { 708 _topology_destroy(db_ref); 709 TOPO_UNLOCK; 710 return BCM_E_MEMORY; 711 } 712 TP_TX_CXN_INIT(db_ref, bytes); 713 714 TP_RX_CXN_MATRIX(db_ref) = sal_alloc(bytes, "topo_rx_matrix"); 715 if (TP_RX_CXN_MATRIX(db_ref) == NULL) { 716 _topology_destroy(db_ref); 717 TOPO_UNLOCK; 718 return BCM_E_MEMORY; 719 } 720 TP_RX_CXN_INIT(db_ref, bytes); 721 722 if (tp_find_cut_ports(db_ref) < 0) { 723 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 724 (BSL_META("TOPO WARNING: Spanning-tree/cut-port failed\n"))); 725 } 726 727 rv = tp_find_paths(db_ref); 728 if (rv < 0) { 729 _topology_destroy(db_ref); 730 TOPO_UNLOCK; 731 return rv; 732 } 733 734 if (!tp_all_destinations_reachable(db_ref)) { 735 _topology_destroy(db_ref); 736 TOPO_UNLOCK; 737 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 738 (BSL_META("TOPO WARNING: Cannot reach all CPUs.\n"))); 739 return BCM_E_FAIL; 740 } 741 742 TOPO_UNLOCK; 743 return BCM_E_NONE; 744 } 745 746 /* 747 * Function: 748 * topology_mod_id_assign_function 749 * Purpose: 750 * Sets the mod id assign funtion to the parameter. If null, 751 * generic_topology_mod_ids_assign() will be used. 752 * Parameters: 753 * func -- (IN) 754 * Returns: 755 * BCM_E_XXX 756 */ 757 int 758 topology_mod_id_assign_function(topology_mod_id_assign_f func) 759 { 760 topology_mod_id_assign_func = func; 761 762 return BCM_E_NONE; 763 } 764 765 /* 766 * Function: 767 * topo_reserved_modid_set 768 * Purpose: 769 * Reserves modid from the available pool, that must not 770 * be used for assigning to devices during stack topology 771 * Parameters: 772 * modid_in_use -- (IN) 773 * Returns: 774 * BCM_E_XXX 775 */ 776 int 777 topo_reserved_modid_set(uint32 modid_in_use, int enable) 778 { 779 780 if (enable) { 781 topo_rsvd_modid |= modid_in_use; 782 } else { 783 topo_rsvd_modid &= ~modid_in_use; 784 } 785 return BCM_E_NONE; 786 } 787 788 /* 789 * Function: 790 * topo_reserved_modid_get 791 * Purpose: 792 * Get the current bitmap of reserved modid's 793 * Parameters: 794 * modid_in_use -- (OUT) 795 * Returns: 796 * BCM_E_XXX 797 */ 798 int 799 topo_reserved_modid_get(uint32 *modid_in_use) 800 { 801 *modid_in_use = topo_rsvd_modid; 802 803 return BCM_E_NONE; 804 } 805 806 /* 807 * Function: 808 * generic_topology_mod_ids_assign 809 * Purpose: 810 * Internal function to assign MODIDs 811 * Notes: 812 * First, try to put all mod ids in by old settings or preference. 813 * Priority given to the value the entry's unit had in old CPU DB; 814 * then to the value in entry->base.pref_mod_id[unit]. After assigning 815 * these, look for any mod id where it fits. 816 */ 817 818 819 820 /* This is restricted to 32 module ID systems */ 821 #define MOD_FREE(_inuse, _mod, _mask) \ 822 (((_inuse) & ((_mask) << (_mod))) == 0) 823 824 STATIC int 825 generic_topology_mod_ids_assign(cpudb_ref_t db_ref) 826 { 827 uint32 modinuse, trymask; 828 int oldmod, prefmod, mod; 829 cpudb_entry_t *entry, *oent; 830 char keybuf[CPUDB_KEY_STRING_LEN]; 831 int unit; 832 int rv = BCM_E_NONE; 833 834 modinuse = topo_rsvd_modid; 835 836 /* Assign as per old CPUDB if present */ 837 if (cpudb_valid(db_ref->old_db)) { 838 CPUDB_FOREACH_ENTRY(db_ref, entry) { 839 CPUDB_KEY_SEARCH(db_ref->old_db, entry->base.key, oent); 840 if (oent == NULL) { /* No entry in old db */ 841 continue; 842 } 843 for (unit = 0; unit < entry->base.num_units; unit++) { 844 if (entry->base.mod_ids_req[unit] <= 0) { 845 continue; 846 } 847 trymask = (1 << entry->base.mod_ids_req[unit]) - 1; 848 oldmod = oent->mod_ids[unit]; 849 if (oldmod >= 0 && MOD_FREE(modinuse, oldmod, trymask)) { 850 modinuse |= (trymask << oldmod); 851 entry->mod_ids[unit] = oldmod; 852 } 853 } 854 } 855 } 856 857 /* Assign as per preference in current DB */ 858 CPUDB_FOREACH_ENTRY(db_ref, entry) { 859 for (unit = 0; unit < entry->base.num_units; unit++) { 860 if (entry->mod_ids[unit] >= 0 || /* Already assigned */ 861 entry->base.mod_ids_req[unit] <= 0) { /* None needed */ 862 continue; 863 } 864 trymask = (1 << entry->base.mod_ids_req[unit]) - 1; 865 prefmod = entry->base.pref_mod_id[unit]; 866 if (prefmod >= 0 && MOD_FREE(modinuse, prefmod, trymask)) { 867 modinuse |= (trymask << prefmod); 868 entry->mod_ids[unit] = prefmod; 869 } 870 } 871 } 872 873 /* Now, fit in anywhere */ 874 CPUDB_FOREACH_ENTRY(db_ref, entry) { 875 for (unit = 0; unit < entry->base.num_units; unit++) { 876 if (entry->mod_ids[unit] >= 0 || /* Already assigned */ 877 entry->base.mod_ids_req[unit] <= 0) { /* None needed */ 878 continue; 879 } 880 for (mod = 0; mod <= (32 - entry->base.mod_ids_req[unit]); mod++) { 881 882 if ((mod & 1) != 0 && 883 entry->base.pref_mod_id[unit] == CPUDB_TOPO_MODID_EVEN) { 884 /* If the unit's modid needs to be even, and 'mod' 885 is odd, then skip this modid. */ 886 continue; 887 } 888 889 trymask = (1 << entry->base.mod_ids_req[unit]) - 1; 890 if (MOD_FREE(modinuse, mod, trymask)) { 891 modinuse |= (trymask << mod); 892 entry->mod_ids[unit] = mod; 893 break; 894 } 895 } 896 897 if (entry->mod_ids[unit] < 0) { 898 cpudb_key_format(entry->base.key, keybuf, sizeof(keybuf)); 899 LOG_WARN(BSL_LS_TKS_TOPOLOGY, 900 (BSL_META_U(unit, 901 "TOPO WARN: no available modids for cpu %s, " 902 "unit %d (needs %d)\n"), keybuf, unit, 903 entry->base.mod_ids_req[unit])); 904 rv = BCM_E_RESOURCE; 905 } 906 } 907 } 908 909 return rv; 910 } 911 912 #undef MOD_FREE 913 914 /* 915 * Function: 916 * topology_mod_ids_assign 917 * Purpose: 918 * Assign module IDs for each unit in the system 919 * Parameters: 920 * db_ref -- (IN/OUT) DB reference to update 921 * Returns: 922 * BCM_E_XXX 923 * Notes: 924 * 925 * This routine does not program any hardware; it only updates the 926 * DB. 927 */ 928 int 929 topology_mod_ids_assign(cpudb_ref_t db_ref) 930 { 931 int unit; 932 cpudb_entry_t *entry; 933 934 /* Clear all mod ids */ 935 CPUDB_FOREACH_ENTRY(db_ref, entry) { 936 for (unit = 0; unit < entry->base.num_units; unit++) { 937 entry->mod_ids[unit] = -1; 938 } 939 } 940 941 return topology_mod_id_assign_func ? 942 topology_mod_id_assign_func(db_ref) : 943 generic_topology_mod_ids_assign(db_ref); 944 } 945 946 /* 947 * Function: 948 * _topology_destroy 949 * Purpose: 950 * Internal function to de-allocate topology info from a CPU DB. 951 */ 952 953 STATIC void 954 _topology_destroy(cpudb_ref_t db_ref) 955 { 956 if (db_ref->topo_cookie != NULL) { 957 if (TP_TX_CXN_MATRIX(db_ref) != NULL) { 958 sal_free(TP_TX_CXN_MATRIX(db_ref)); 959 } 960 if (TP_RX_CXN_MATRIX(db_ref) != NULL) { 961 sal_free(TP_RX_CXN_MATRIX(db_ref)); 962 } 963 sal_free(db_ref->topo_cookie); 964 db_ref->topo_cookie = NULL; 965 } 966 } 967 968 /* 969 * Function: 970 * topology_destroy 971 * Purpose: 972 * De-allocate the topology associated with a DB reference 973 * Parameters: 974 * db_ref - The DB to update 975 * Returns: 976 * BCM_E_XXX 977 */ 978 979 int 980 topology_destroy(cpudb_ref_t db_ref) 981 { 982 TOPO_LOCK_INIT; 983 TOPO_LOCK_CHECK; 984 985 TOPO_LOCK; 986 _topology_destroy(db_ref); 987 TOPO_UNLOCK; 988 989 return BCM_E_NONE; 990 } 991 992 /* 993 * Function: 994 * topo_tx_port_get 995 * Purpose: 996 * Get the transmit port to send a pkt from src to dest 997 * Parameters: 998 * db_ref - DB reference to use 999 * src_entry - Source CPU entry 1000 * dest_entry - Destination CPU entry 1001 * stk_idx - (OUT) Stack port index in src_entry to use 1002 * Returns: 1003 * BCM_E_INIT - Topology DB not initialized 1004 * BCM_E_NOT_FOUND - Could not find source or dest key in db 1005 * BCM_E_FAIL - Connection not found; either dest key is not 1006 * found or connection not possible. 1007 * BCM_E_NONE - Success 1008 */ 1009 1010 int 1011 topo_tx_port_get(cpudb_ref_t db_ref, 1012 cpudb_entry_t *src_entry, 1013 cpudb_entry_t *dest_entry, 1014 int *stk_idx) 1015 { 1016 uint8 cxn; 1017 1018 if (db_ref->topo_cookie == NULL) { 1019 /* Doesn't look like analysis is done */ 1020 return BCM_E_INIT; 1021 } 1022 1023 cxn = TP_TX_CXN(db_ref, src_entry->topo_idx, dest_entry->topo_idx); 1024 if (cxn == TOPO_CXN_UNKNOWN) { 1025 return BCM_E_FAIL; 1026 } 1027 1028 *stk_idx = cxn; 1029 return BCM_E_NONE; 1030 }