field_prio.c (16860B)
1 /* 2 * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 3 * 4 * Copyright 2007-2019 Broadcom Inc. All rights reserved. 5 * 6 * File: field_prio.c 7 * Purpose: FP entry priority handling (for entries in External TCAM) 8 */ 9 10 #include <soc/mem.h> 11 #include <soc/debug.h> 12 #include <soc/drv.h> 13 #include <soc/cmic.h> 14 #include <soc/field.h> 15 16 #ifdef BCM_FIELD_SUPPORT 17 #include <bcm/error.h> 18 #include <bcm/field.h> 19 #include <bcm_int/esw/field.h> 20 #if defined(BCM_TRIUMPH_SUPPORT) 21 #include <bcm/l2.h> 22 #include <bcm/l3.h> 23 #include <bcm/vlan.h> 24 #include <bcm_int/esw/mbcm.h> 25 #include <bcm_int/esw/l3.h> 26 #include <bcm_int/esw/triumph.h> 27 #endif /* BCM_TRIUMPH_SUPPORT */ 28 #if defined(BCM_TRIUMPH3_SUPPORT) 29 #include <bcm_int/esw/triumph3.h> 30 #endif /* BCM_TRIUMPH3_SUPPORT */ 31 32 33 /* 34 * Function: 35 * _bcm_field_prio_mgmt_init 36 * Purpose: 37 * Allocate memory for priority management 38 * Parameters: 39 * unit - (IN) BCM unit 40 * stage_fc - (IN) Stage 41 * Returns: 42 * BCM_E_NONE - Success 43 * BCM_E_MEMORY - No memory 44 * Notes: 45 * Used only for External TCAM 46 */ 47 int 48 _bcm_field_prio_mgmt_init(int unit, _field_stage_t *stage_fc) 49 { 50 int i; 51 _field_prio_mgmt_t *prio_temp; 52 53 if (stage_fc->stage_id != _BCM_FIELD_STAGE_EXTERNAL) { 54 return (BCM_E_NONE); 55 } 56 57 for (i = 0; i < stage_fc->tcam_slices; i++) { 58 59 prio_temp = sal_alloc(sizeof (struct _field_prio_mgmt_s), 60 "Entry prio mgmt"); 61 if (prio_temp == NULL) { 62 _bcm_field_prio_mgmt_deinit(unit, stage_fc); 63 return (BCM_E_MEMORY); 64 } 65 66 prio_temp->prio = BCM_FIELD_ENTRY_PRIO_LOWEST; 67 prio_temp->start_index = 0; 68 prio_temp->end_index = 69 stage_fc->slices[_FP_DEF_INST][i].entry_count - 1; 70 prio_temp->num_free_entries = 71 stage_fc->slices[_FP_DEF_INST][i].entry_count; 72 prio_temp->prev = NULL; 73 prio_temp->next = NULL; 74 75 stage_fc->slices[_FP_DEF_INST][i].prio_mgmt = prio_temp; 76 } 77 78 return (BCM_E_NONE); 79 } 80 81 /* 82 * Function: 83 * _bcm_field_prio_mgmt_deinit 84 * Purpose: 85 * Free memory used for priority management 86 * Parameters: 87 * unit - (IN) BCM unit 88 * stage_fc - (IN) Stage 89 * Returns: 90 * BCM_E_NONE - Success 91 * Notes: 92 * Used only for External TCAM 93 */ 94 int 95 _bcm_field_prio_mgmt_deinit(int unit, _field_stage_t *stage_fc) 96 { 97 int i; 98 _field_prio_mgmt_t *prio1, *prio2; 99 100 if (stage_fc->stage_id != _BCM_FIELD_STAGE_EXTERNAL) { 101 return (BCM_E_NONE); 102 } 103 104 for (i = 0; i < stage_fc->tcam_slices; i++) { 105 prio1 = stage_fc->slices[_FP_DEF_INST][i].prio_mgmt; 106 while (prio1 != NULL) { 107 prio2 = prio1->next; 108 sal_free(prio1); 109 prio1 = prio2; 110 } 111 stage_fc->slices[_FP_DEF_INST][i].prio_mgmt = NULL; 112 } 113 114 return (BCM_E_NONE); 115 } 116 117 /* 118 * Function: 119 * _field_prio_mgmt_move 120 * Purpose: 121 * Move f_ent from index1 to index2 122 * Parameters: 123 * unit - (IN) BCM unit 124 * f_ent - (IN) Entry to be moved 125 * index1 - (IN) source index 126 * index2 - (IN) destination index 127 * Returns: 128 * none 129 * Notes: 130 * Used only for External TCAM 131 * It is the calling function's responsibility to 132 * update the prio_mgmt structure. 133 */ 134 void 135 _field_prio_mgmt_move(int unit, _field_entry_t *f_ent, int index1, int index2) 136 { 137 #if defined (BCM_TRIUMPH3_SUPPORT) 138 if (SOC_IS_TRIUMPH3(unit)) { 139 _bcm_field_tr3_external_entry_move(unit, f_ent, index1, index2); 140 return; 141 } 142 #endif /* BCM_TRIUMPH3_SUPPORT */ 143 #if defined (BCM_TRIUMPH_SUPPORT) 144 if (SOC_IS_TRIUMPH(unit) || SOC_IS_TRIUMPH2(unit)) { 145 _bcm_field_tr_external_entry_move(unit, f_ent, index1, index2); 146 return; 147 } 148 #endif /* BCM_TRIUMPH_SUPPORT */ 149 } 150 151 /* 152 * Function: 153 * _field_prio_mgmt_shift_prev 154 * Purpose: 155 * Create an empty slot in target_node 156 * Parameters: 157 * unit - (IN) BCM unit 158 * stage_fc - (IN) Stage 159 * slice_numb - (IN) Slice under consideration 160 * prev_free_node - (IN) prev node which has a free slot 161 * target_node - (IN) node where an empty slot needs to be created 162 * Returns: 163 * none 164 */ 165 void 166 _field_prio_mgmt_shift_prev(int unit, _field_stage_t *stage_fc, int slice_numb, 167 _field_prio_mgmt_t *prev_free_node, 168 _field_prio_mgmt_t *target_node) 169 { 170 _field_prio_mgmt_t *node1, *node2; 171 172 node1 = prev_free_node; 173 node2 = target_node; 174 175 node1->end_index--; 176 node1->num_free_entries--; 177 178 node1->next->start_index--; 179 node1->next->num_free_entries++; 180 181 node1 = node1->next; 182 183 while (node1 != node2) { 184 _field_prio_mgmt_move(unit, 185 stage_fc->slices[_FP_DEF_INST][slice_numb] 186 .entries[node1->end_index], 187 node1->end_index, node1->start_index); 188 189 node1->end_index--; 190 node1->num_free_entries--; 191 192 node1->next->start_index--; 193 node1->next->num_free_entries++; 194 195 node1 = node1->next; 196 } 197 } 198 199 /* 200 * Function: 201 * _field_prio_mgmt_shift_next 202 * Purpose: 203 * Create an empty slot in target_node 204 * Parameters: 205 * unit - (IN) BCM unit 206 * stage_fc - (IN) Stage 207 * slice_numb - (IN) Slice under consideration 208 * target_node - (IN) node where an empty slot needs to be created 209 * next_free_node - (IN) next node which has a free slot 210 * Returns: 211 * none 212 */ 213 void 214 _field_prio_mgmt_shift_next(int unit, _field_stage_t *stage_fc, int slice_numb, 215 _field_prio_mgmt_t *target_node, 216 _field_prio_mgmt_t *next_free_node) 217 { 218 _field_prio_mgmt_t *node1, *node2; 219 220 node1 = target_node; 221 node2 = next_free_node; 222 223 while (node2 != node1) { 224 if ((node2->end_index - node2->start_index + 1) > 225 (node2->num_free_entries)) { 226 _field_prio_mgmt_move(unit, 227 stage_fc->slices[_FP_DEF_INST][slice_numb] 228 .entries[node2->start_index], 229 node2->start_index, 230 node2->end_index + 1 - node2->num_free_entries); 231 } 232 233 node2->start_index++; 234 node2->num_free_entries--; 235 236 node2->prev->end_index++; 237 node2->prev->num_free_entries++; 238 239 node2 = node2->prev; 240 } 241 242 /* 243 * Now it is guaranteed that there is a free slot at 244 * target_node->end_index 245 * Also, target_node == node1 == node2 now. 246 * See comment after the calling location 247 */ 248 _field_prio_mgmt_move(unit, 249 stage_fc->slices[_FP_DEF_INST][slice_numb].entries[node2->start_index], 250 node2->start_index, node2->end_index); 251 } 252 253 /* 254 * Function: 255 * _bcm_field_entry_target_location 256 * Purpose: 257 * Find the target location for an entry, given its location 258 * Parameters: 259 * unit - (IN) BCM unit 260 * stage_fc - (IN) Stage 261 * f_ent - (IN) Entry whose target location needs to be found 262 * new_prio - (IN) new priority of the entry 263 * new_location - (OUT) target location 264 * Returns: 265 * BCM_E_NONE - Success 266 * Notes: 267 * - Used only for External TCAM 268 * - This may involve moving entries in the slice 269 * - There is some more scope for optimization, in the main ELSE clause 270 * e.g. instead of getting 1 entry, try for more. 271 */ 272 int 273 _bcm_field_entry_target_location(int unit, _field_stage_t *stage_fc, 274 _field_entry_t *f_ent, int new_prio, 275 uint32 *new_location) 276 { 277 _field_prio_mgmt_t *list, *target_node, *node; 278 _field_prio_mgmt_t *prev_free_node, *next_free_node; 279 int prev_free_dist, next_free_dist; 280 int slice_numb; 281 282 prev_free_node = next_free_node = NULL; 283 prev_free_dist = next_free_dist = 0; 284 285 slice_numb = f_ent->fs->slice_number; 286 list = stage_fc->slices[_FP_DEF_INST][slice_numb].prio_mgmt; 287 288 while (list != NULL) { 289 if (_field_entry_prio_cmp(list->prio, new_prio) <= 0) { 290 break; 291 } 292 if (list->num_free_entries > 0) { 293 prev_free_node = list; 294 prev_free_dist = 0; 295 } else { 296 prev_free_dist++; /* Valid only if prev_free_node != NULL */ 297 } 298 list = list->next; 299 } 300 301 assert(list != NULL); 302 303 target_node = list; 304 305 /* 306 * COVERITY 307 * 308 * assert passes only when list is not NULL 309 */ 310 /* coverity[var_deref_op : FALSE] */ 311 list = list->next; 312 /* Find next free node */ 313 while (list != NULL) { 314 next_free_dist++; /* Valid only if next_free_node != NULL */ 315 if (list->num_free_entries > 0) { 316 next_free_node = list; 317 break; 318 } 319 list = list->next; 320 } 321 322 /* See if target_node has free entries */ 323 if (target_node->num_free_entries > 0) { 324 /* 325 * If priority is same, use an empty slot 326 * OPTIMIZATION: as packed, use the next free index 327 */ 328 if (target_node->prio == new_prio) { 329 *new_location = target_node->end_index + 1 - 330 target_node->num_free_entries; 331 } 332 /* 333 * Otherwise, divide this node into 2 regions 334 */ 335 else { 336 /* 337 * See if there are any entries. 338 * If so, Move entry at target_node->start_index to an empty slot 339 * OPTIMIZATION: as packed, use the next free index 340 */ 341 if ((target_node->end_index - target_node->start_index + 1) > 342 (target_node->num_free_entries)) { 343 _field_prio_mgmt_move(unit, 344 stage_fc->slices[_FP_DEF_INST][slice_numb]. 345 entries[target_node->start_index], 346 target_node->start_index, 347 target_node->end_index + 1 - target_node->num_free_entries); 348 } 349 350 /* Now form a new node with only 1 entry */ 351 node = sal_alloc(sizeof(struct _field_prio_mgmt_s), "prio node"); 352 if (node == NULL) { 353 return (BCM_E_MEMORY); 354 } 355 node->prio = new_prio; 356 357 node->start_index = node->end_index = target_node->start_index; 358 *new_location = node->start_index; 359 target_node->start_index++; 360 361 node->num_free_entries = 1; 362 target_node->num_free_entries--; 363 364 node->prev = target_node->prev; 365 if (node->prev == NULL) { 366 stage_fc->slices[_FP_DEF_INST][slice_numb].prio_mgmt = node; 367 } else { 368 node->prev->next = node; 369 } 370 node->next = target_node; 371 target_node->prev = node; 372 } 373 } else { 374 if (prev_free_node != NULL) { 375 if (next_free_node != NULL) { 376 if (prev_free_dist <= next_free_dist) { 377 _field_prio_mgmt_shift_prev(unit, stage_fc, slice_numb, 378 prev_free_node, target_node); 379 } else { 380 _field_prio_mgmt_shift_next(unit, stage_fc, slice_numb, 381 target_node, next_free_node); 382 } 383 } else { 384 _field_prio_mgmt_shift_prev(unit, stage_fc, slice_numb, 385 prev_free_node, target_node); 386 } 387 } else { 388 if (next_free_node != NULL) { 389 _field_prio_mgmt_shift_next(unit, stage_fc, slice_numb, 390 target_node, next_free_node); 391 } else { 392 return (BCM_E_RESOURCE); 393 } 394 } 395 /* 396 * Now an empty slot is created at the 397 * target_node->start_index 398 * NOTE: for new_prio == target_node->prio, 1 shift could 399 * be avoided if the empty slot was created at the end, 400 * when shift_next was being used. 401 * BUT for uniformity with new_prio != target_node->prio, 402 * and with shift_prev, we don't do this. 403 */ 404 *new_location = target_node->start_index; 405 406 if (target_node->prio != new_prio) { 407 /* Form a new node */ 408 node = sal_alloc(sizeof(struct _field_prio_mgmt_s), "prio node"); 409 if (node == NULL) { 410 return (BCM_E_MEMORY); 411 } 412 node->prio = new_prio; 413 414 node->start_index = node->end_index = target_node->start_index; 415 target_node->start_index++; 416 417 node->num_free_entries = 1; 418 target_node->num_free_entries = 0; 419 420 node->prev = target_node->prev; 421 if (node->prev == NULL) { 422 stage_fc->slices[_FP_DEF_INST][slice_numb].prio_mgmt = node; 423 } else { 424 node->prev->next = node; 425 } 426 node->next = target_node; 427 target_node->prev = node; 428 } 429 } 430 return (BCM_E_NONE); 431 } 432 433 /* 434 * Function: 435 * _bcm_field_entry_prio_mgmt_update 436 * Purpose: 437 * Updates the prio_mgmt structure 438 * Parameters: 439 * unit - (IN) unit 440 * f_ent - (IN) entry which was installed/removed 441 * flag - (IN) +1 = Install, -1 = Remove 442 * old_location - (IN) Valid only if flag == -1 443 * Location from which entry is/was removed. 444 * is: entry_remove; was: prio_set 445 * Returns: 446 * none 447 * Notes: 448 * Can optimize to collapse a node if all its entries are free 449 */ 450 int 451 _bcm_field_entry_prio_mgmt_update(int unit, _field_entry_t *f_ent, 452 int flag, uint32 old_location) 453 { 454 _field_stage_t *stage_fc; 455 _field_prio_mgmt_t *list; 456 int prio; 457 458 BCM_IF_ERROR_RETURN 459 (_field_stage_control_get(unit, f_ent->fs->stage_id, &stage_fc)); 460 461 list = f_ent->fs->prio_mgmt; 462 prio = f_ent->prio; 463 464 while (list != NULL) { 465 if (list->prio == prio) { 466 break; 467 } 468 list = list->next; 469 } 470 if (list == NULL) { 471 return (BCM_E_INTERNAL); 472 } 473 474 if (flag == 1) { 475 list->num_free_entries--; 476 } else { 477 /* 478 * Pack the enties in this priority class 479 * Move the bottom most entry to old_location 480 * unless old_location was bottom most (may be last) 481 */ 482 if (old_location != (list->end_index - list->num_free_entries)) { 483 _field_prio_mgmt_move(unit, 484 stage_fc->slices[_FP_DEF_INST][f_ent->fs->slice_number]. 485 entries[list->end_index - list->num_free_entries], 486 list->end_index - list->num_free_entries, 487 old_location); 488 } 489 490 list->num_free_entries++; 491 } 492 return (BCM_E_NONE); 493 } 494 495 496 /* Rebuild the linked list of entry indices spanned by priorities 497 */ 498 499 int 500 _bcm_field_prio_mgmt_slice_reinit(int unit, 501 _field_stage_t *stage_fc, 502 _field_slice_t *fs 503 ) 504 { 505 unsigned eidx; 506 _field_entry_t *f_ent; 507 _field_prio_mgmt_t *lastnode, *newnode, *temp_node; 508 509 /* Free the memory allocated during init */ 510 while (fs->prio_mgmt) { 511 temp_node = fs->prio_mgmt->next; 512 sal_free(fs->prio_mgmt); 513 fs->prio_mgmt = temp_node; 514 } 515 fs->prio_mgmt = NULL; 516 517 /* Scan all entries in slice */ 518 519 for (lastnode = 0, eidx = 0; eidx < fs->entry_count; ++eidx) { 520 f_ent = fs->entries[eidx]; 521 if ((lastnode == 0) || (lastnode->prio != 0) || (f_ent && f_ent->prio != lastnode->prio)) { 522 /* Create entry-index-span node */ 523 524 newnode = (struct _field_prio_mgmt_s *) 525 sal_alloc(sizeof(*newnode), "Entry prio mgmt"); 526 527 if (newnode == 0) { 528 return (BCM_E_MEMORY); 529 } 530 531 /* Priority of entries in this span */ 532 newnode->prio = f_ent ? f_ent->prio : 0; 533 /* Span starts here */ 534 newnode->start_index = eidx; 535 /* No free entries yet */ 536 newnode->num_free_entries = 0; 537 538 /* Hook in new span node */ 539 540 *(lastnode ? &lastnode->next : &fs->prio_mgmt) = newnode; 541 newnode->prev = lastnode; 542 newnode->next = 0; 543 544 lastnode = newnode; 545 } 546 547 if (f_ent == 0) { 548 /* Entry not in use */ 549 550 ++lastnode->num_free_entries; 551 } 552 553 lastnode->end_index = eidx; 554 } 555 556 return (BCM_E_NONE); 557 } 558 559 #endif /* BCM_FIELD_SUPPORT */ 560