alpm_trie_v6.c (95302B)
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 * File: trie_v6.c 7 * Purpose: Custom Trie Data structure 8 * Requires: 9 */ 10 11 #include <soc/types.h> 12 #include <soc/drv.h> 13 #include <shared/bsl.h> 14 #ifdef ALPM_ENABLE 15 #ifdef BCM_TRIDENT2_SUPPORT 16 #include <shared/util.h> 17 #include <sal/appl/sal.h> 18 #include <sal/core/libc.h> 19 #include <sal/core/time.h> 20 #include <soc/esw/trie.h> 21 #include <soc/esw/trie_util.h> 22 #include <soc/esw/sbDq.h> 23 24 #define _MAX_KEY_LEN_ (_MAX_KEY_LEN_144_) 25 #define _MAX_KEY_WORDS_ (BITS2WORDS(_MAX_KEY_LEN_)) 26 27 /* key packing expetations: 28 * eg., 144 bit key 29 * - 0x10/8 -> key[0]=0, key[1]=0, key[2]=0, key[3]=0, key[0]=0x10 30 * - 0x123456789a/48 -> key[0]=0, key[1]=0, key[2]=0, key[3] = 0x12 key[4] = 0x3456789a 31 * length - represents number of valid bits from farther to lower index ie., 1->0 32 */ 33 #define KEY_BIT2IDX(x) (((BITS2WORDS(_MAX_KEY_LEN_)*32) - (x))/32) 34 35 36 /********************************************************/ 37 /* Get a chunk of bits from a key (MSB bit - on word0, lsb on word 1).. 38 */ 39 static unsigned int _key_get_bits(unsigned int *key, 40 unsigned int pos /* 1based, msb bit position */, 41 unsigned int len, 42 unsigned int skip_len_check) 43 { 44 /* coverity[var_deref_op : FALSE] */ 45 if (!key || (pos < len) || (pos > _MAX_KEY_LEN_) || 46 ((skip_len_check == TRUE) && (len > _MAX_SKIP_LEN_))) { 47 assert(0); 48 } 49 50 /* use Macro, convert to what's required by Macro */ 51 return _TAPS_GET_KEY_BITS(key, pos-len, len, _MAX_KEY_LEN_); 52 } 53 54 /* 55 * Assumes the layout for 56 * 0 - most significant word 57 * _MAX_KEY_WORDS_ - least significant word 58 * eg., for key size of 48, word0-[bits 48-32] word1-[bits31-0] 59 */ 60 static int _key_append(unsigned int *key, 61 unsigned int *length, 62 unsigned int skip_addr, 63 unsigned int skip_len) 64 { 65 int rv=SOC_E_NONE; 66 67 if (!key || !length || ((skip_len + *length) > _MAX_KEY_LEN_) || 68 (skip_len > _MAX_SKIP_LEN_) ) { 69 return SOC_E_PARAM; 70 } 71 72 rv = taps_key_shift(_MAX_KEY_LEN_, key, *length, 0-(int)skip_len); 73 if (SOC_SUCCESS(rv)) { 74 key[KEY_BIT2IDX(1)] |= skip_addr; 75 *length += skip_len; 76 } 77 78 return rv; 79 } 80 81 static int _bpm_append(unsigned int *key, 82 unsigned int *length, 83 unsigned int skip_addr, 84 unsigned int skip_len) 85 { 86 int rv=SOC_E_NONE; 87 88 if (!key || !length || ((skip_len + *length) > _MAX_KEY_LEN_) || 89 (skip_len > (_MAX_SKIP_LEN_+1)) ) { 90 return SOC_E_PARAM; 91 } 92 93 rv = taps_key_shift(_MAX_KEY_LEN_, key, *length, 0-(int)skip_len); 94 if (SOC_SUCCESS(rv)) { 95 key[KEY_BIT2IDX(1)] |= skip_addr; 96 *length += skip_len; 97 } 98 99 return rv; 100 } 101 102 /* 103 * Function: 104 * lcplen 105 * Purpose: 106 * returns longest common prefix length provided a key & skip address 107 */ 108 unsigned int 109 static lcplen(unsigned int *key, unsigned int len1, 110 unsigned int skip_addr, unsigned int len2) 111 { 112 unsigned int diff; 113 unsigned int lcp = len1 < len2 ? len1 : len2; 114 115 if ((len1 > _MAX_KEY_LEN_) || (len2 > _MAX_KEY_LEN_)) { 116 LOG_CLI((BSL_META("len1 %d or len2 %d is larger than %d\n"), 117 len1, len2, _MAX_KEY_LEN_)); 118 assert(0); 119 } 120 121 if ((len1 == 0) || (len2 == 0)) { 122 return 0; 123 } 124 125 diff = _key_get_bits(key, len1, lcp, TRUE); 126 diff ^= (SHR(skip_addr, len2 - lcp, _MAX_SKIP_LEN_) & MASK(lcp)); 127 128 while (diff) { 129 diff >>= 1; 130 --lcp; 131 } 132 133 return lcp; 134 } 135 136 int _trie_v6_search(trie_node_t *trie, 137 unsigned int *key, 138 unsigned int length, 139 trie_node_t **payload, 140 unsigned int *result_key, 141 unsigned int *result_len, 142 unsigned int dump, 143 unsigned int find_pivot) 144 { 145 unsigned int lcp=0; 146 int bit=0, rv=SOC_E_NONE; 147 148 if (!trie || (length && trie->skip_len && !key)) return SOC_E_PARAM; 149 if ((result_key && !result_len) || (!result_key && result_len)) return SOC_E_PARAM; 150 151 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 152 153 if (dump) { 154 _print_trie_node(trie, (unsigned int *)1); 155 } 156 157 if (length > trie->skip_len) { 158 if (lcp == trie->skip_len) { 159 bit = (key[KEY_BIT2IDX(length - lcp)] & \ 160 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 161 if (dump) { 162 LOG_CLI((BSL_META(" Length: %d Next-Bit[%d] \n"), length, bit)); 163 } 164 165 if (result_key) { 166 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 167 if (SOC_FAILURE(rv)) return rv; 168 } 169 170 /* based on next bit branch left or right */ 171 if (trie->child[bit].child_node) { 172 if (result_key) { 173 rv = _key_append(result_key, result_len, bit, 1); 174 if (SOC_FAILURE(rv)) return rv; 175 } 176 177 return _trie_v6_search(trie->child[bit].child_node, key, 178 length - lcp - 1, payload, 179 result_key, result_len, dump, find_pivot); 180 } else { 181 return SOC_E_NOT_FOUND; /* not found */ 182 } 183 } else { 184 return SOC_E_NOT_FOUND; /* not found */ 185 } 186 } else if (length == trie->skip_len) { 187 if (lcp == length) { 188 if (dump) { 189 LOG_CLI((BSL_META(": MATCH \n"))); 190 } 191 *payload = trie; 192 if (trie->type != PAYLOAD && !find_pivot) { 193 /* no assert here, possible during dbucket search 194 * due to 1* and 0* bucket search 195 */ 196 return SOC_E_NOT_FOUND; 197 } 198 if (result_key) { 199 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 200 if (SOC_FAILURE(rv)) return rv; 201 } 202 return SOC_E_NONE; 203 } 204 else return SOC_E_NOT_FOUND; 205 } else { 206 if (lcp == length && find_pivot) { 207 *payload = trie; 208 if (result_key) { 209 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 210 if (SOC_FAILURE(rv)) return rv; 211 } 212 } 213 return SOC_E_NOT_FOUND; /* not found */ 214 } 215 } 216 217 /* 218 * Internal function for LPM match searching. 219 * callback on all payload nodes if cb != NULL. 220 */ 221 int _trie_v6_find_lpm(trie_node_t *trie, 222 unsigned int *key, 223 unsigned int length, 224 trie_node_t **payload, 225 trie_callback_f cb, 226 void *user_data, 227 unsigned int exclude_self) 228 { 229 unsigned int lcp=0; 230 int bit=0, rv=SOC_E_NONE; 231 232 if (!trie || (length && trie->skip_len && !key)) return SOC_E_PARAM; 233 234 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 235 236 if ((length > trie->skip_len) && (lcp == trie->skip_len)) { 237 if (trie->type == PAYLOAD) { 238 /* lpm cases */ 239 if (payload != NULL) { 240 /* update lpm result */ 241 *payload = trie; 242 } 243 244 if (cb != NULL) { 245 /* callback with any nodes which is shorter and matches the prefix */ 246 rv = cb(trie, user_data); 247 if (SOC_FAILURE(rv)) { 248 /* early bailout if there is error in callback handling */ 249 return rv; 250 } 251 } 252 } 253 254 bit = (key[KEY_BIT2IDX(length - lcp)] & \ 255 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 256 257 /* based on next bit branch left or right */ 258 if (trie->child[bit].child_node) { 259 return _trie_v6_find_lpm(trie->child[bit].child_node, key, length - lcp - 1, 260 payload, cb, user_data, exclude_self); 261 } 262 } else if ((length == trie->skip_len) && (lcp == length)) { 263 if (trie->type == PAYLOAD) { 264 /* exact match case */ 265 if (payload != NULL && !exclude_self) { 266 /* lpm is exact match */ 267 *payload = trie; 268 } 269 270 if (cb != NULL) { 271 /* callback with the exact match node */ 272 rv = cb(trie, user_data); 273 if (SOC_FAILURE(rv)) { 274 /* early bailout if there is error in callback handling */ 275 return rv; 276 } 277 } 278 } 279 } 280 return rv; 281 } 282 283 /* trie->bpm format: 284 * bit 0 is for the pivot itself (longest) 285 * bit skip_len is for the trie branch leading to the pivot node (shortest) 286 * bits (0-skip_len) is for the routes in the parent node's bucket 287 */ 288 int _trie_v6_find_bpm(trie_node_t *trie, 289 unsigned int *key, 290 unsigned int length, 291 int *bpm_length) 292 { 293 unsigned int lcp=0, local_bpm_mask=0; 294 int bit=0, rv=SOC_E_NONE, local_bpm=0; 295 296 if (!trie || (length && trie->skip_len && !key) || 297 (length > _MAX_KEY_LEN_)) return SOC_E_PARAM; 298 299 /* calculate number of matching msb bits */ 300 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 301 302 if (length > trie->skip_len) { 303 if (lcp == trie->skip_len) { 304 /* fully matched and more bits to check, go down the trie */ 305 bit = (key[KEY_BIT2IDX(length - lcp)] & \ 306 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 307 308 if (trie->child[bit].child_node) { 309 rv = _trie_v6_find_bpm(trie->child[bit].child_node, key, length - lcp - 1, bpm_length); 310 /* on the way back, start bpm_length accumulation when encounter first non-0 bpm */ 311 if (*bpm_length >= 0) { 312 /* child node has non-zero bpm, just need to accumulate skip_len and branch bit */ 313 *bpm_length += (trie->skip_len+1); 314 return rv; 315 } else if (trie->bpm & BITMASK(trie->skip_len+1)) { 316 /* first non-zero bmp on the way back */ 317 BITGETLSBSET(trie->bpm, trie->skip_len, local_bpm); 318 if (local_bpm >= 0) { 319 *bpm_length = trie->skip_len - local_bpm; 320 } 321 } 322 /* on the way back, and so far all bpm are 0 */ 323 return rv; 324 } 325 } 326 } 327 328 /* no need to go further, we find whatever bits matched and 329 * check that part of the bpm mask 330 */ 331 local_bpm_mask = trie->bpm & (~(BITMASK(trie->skip_len-lcp))); 332 if (local_bpm_mask & BITMASK(trie->skip_len+1)) { 333 /* first non-zero bmp on the way back */ 334 BITGETLSBSET(local_bpm_mask, trie->skip_len, local_bpm); 335 if (local_bpm >= 0) { 336 *bpm_length = trie->skip_len - local_bpm; 337 } 338 } 339 340 return rv; 341 } 342 343 int _trie_v6_bpm_mask_get(trie_node_t *trie, 344 unsigned int *key, 345 unsigned int length, 346 unsigned int *bpm_mask) 347 { 348 unsigned int lcp=0, scratch=0; 349 int bit=0, rv=SOC_E_NONE; 350 351 if (!trie || (length > _MAX_KEY_LEN_)) return SOC_E_PARAM; 352 353 /* calculate number of matching msb bits */ 354 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 355 356 if (length > trie->skip_len) { 357 if (lcp == trie->skip_len) { 358 /* fully matched and more bits to check, go down the trie */ 359 bit = (key[KEY_BIT2IDX(length - lcp)] & \ 360 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 361 362 if (trie->child[bit].child_node) { 363 _bpm_append(bpm_mask, &scratch, trie->bpm, trie->skip_len + 1); 364 rv = _trie_v6_bpm_mask_get(trie->child[bit].child_node, key, length - lcp - 1, bpm_mask); 365 return rv; 366 } 367 } 368 } 369 370 _bpm_append(bpm_mask, &scratch, trie->bpm, trie->skip_len + 1); 371 372 return rv; 373 } 374 375 /* 376 * Function: 377 * _trie_v6_skip_node_free 378 * Purpose: 379 * Destroy a chain of trie_node_t that has the target node at the end. 380 * The target node is not necessarily PAYLOAD type, but all nodes 381 * on the chain except for the end must have only one branch. 382 * Input: 383 * key -- target key 384 * length -- target key length 385 * free_end -- free 386 */ 387 int _trie_v6_skip_node_free(trie_node_t *trie, 388 unsigned int *key, 389 unsigned int length) 390 { 391 unsigned int lcp=0; 392 int bit=0, rv=SOC_E_NONE; 393 394 if (!trie || (length && trie->skip_len && !key)) return SOC_E_PARAM; 395 396 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 397 398 399 if (length > trie->skip_len) { 400 401 if (lcp == trie->skip_len) { 402 bit = (key[KEY_BIT2IDX(length - lcp)] & \ 403 (1 << ((length - lcp - 1) % _NUM_WORD_BITS_))) ? 1:0; 404 405 /* There should be only one branch on the chain until the end node */ 406 if (!trie->child[0].child_node == !trie->child[1].child_node) { 407 return SOC_E_PARAM; 408 } 409 410 /* based on next bit branch left or right */ 411 if (trie->child[bit].child_node) { 412 rv = _trie_v6_skip_node_free(trie->child[bit].child_node, key, 413 length - lcp - 1); 414 if (SOC_SUCCESS(rv)) { 415 assert(trie->type == INTERNAL); 416 sal_free(trie); 417 } 418 return rv; 419 } else { 420 return SOC_E_NOT_FOUND; /* not found */ 421 } 422 } else { 423 return SOC_E_NOT_FOUND; /* not found */ 424 } 425 } else if (length == trie->skip_len) { 426 if (lcp == length) { 427 /* the end node is not necessarily type payload. */ 428 429 return SOC_E_NONE; 430 } 431 else return SOC_E_NOT_FOUND; 432 } else { 433 return SOC_E_NOT_FOUND; /* not found */ 434 } 435 } 436 437 438 /* 439 * Function: 440 * _trie_v6_skip_node_alloc 441 * Purpose: 442 * create a chain of trie_node_t that has the payload at the end. 443 * each node in the chain can skip upto _MAX_SKIP_LEN number of bits, 444 * while the child pointer in the chain represent 1 bit. So totally 445 * each node can absorb (_MAX_SKIP_LEN+1) bits. 446 * Input: 447 * key -- 448 * bpm -- 449 * msb -- 450 * skip_len -- skip_len of the whole chain 451 * payload -- payload node we want to insert 452 * count -- child count 453 * Output: 454 * node -- return pointer of the starting node of the chain. 455 */ 456 int _trie_v6_skip_node_alloc(trie_node_t **node, 457 unsigned int *key, 458 /* bpm bit map if bpm management is required, passing null skips bpm management */ 459 unsigned int *bpm, 460 unsigned int msb, /* NOTE: valid msb position 1 based, 0 means skip0/0 node */ 461 unsigned int skip_len, 462 trie_node_t *payload, 463 unsigned int count) /* payload count underneath - mostly 1 except some tricky cases */ 464 { 465 int lsb=0, msbpos=0, lsbpos=0, bit=0, index; 466 trie_node_t *child = NULL, *skip_node = NULL; 467 468 /* calculate lsb bit position, also 1 based */ 469 lsb = ((msb)? msb + 1 - skip_len : msb); 470 471 assert(((int)msb >= 0) && (lsb >= 0)); 472 473 if (!node || !key || !payload || msb > _MAX_KEY_LEN_ || msb < skip_len) return SOC_E_PARAM; 474 475 if (msb) { 476 for (index = BITS2SKIPOFF(lsb), lsbpos = lsb - 1; index <= BITS2SKIPOFF(msb); index++) { 477 /* each loop process _MAX_SKIP_LEN number of bits?? */ 478 if (lsbpos == lsb-1) { 479 /* (lsbpos == lsb-1) is only true for first node (loop) here */ 480 skip_node = payload; 481 } else { 482 /* other nodes need to be created */ 483 skip_node = sal_alloc(sizeof(trie_node_t), "trie_node"); 484 } 485 486 /* init memory */ 487 sal_memset(skip_node, 0, sizeof(trie_node_t)); 488 489 /* calculate msb bit position of current chunk of bits we are processing */ 490 msbpos = index * _MAX_SKIP_LEN_ - 1; 491 if (msbpos > msb-1) msbpos = msb-1; 492 493 /* calculate the skip_len of the created node */ 494 if (msbpos - lsbpos < _MAX_SKIP_LEN_) { 495 skip_node->skip_len = msbpos - lsbpos + 1; 496 } else { 497 skip_node->skip_len = _MAX_SKIP_LEN_; 498 } 499 500 /* calculate the skip_addr (skip_length number of bits). 501 * skip might be skipping bits on 2 different words 502 * if msb & lsb spawns 2 word boundary in worst case 503 */ 504 if (BITS2WORDS(msbpos+1) != BITS2WORDS(lsbpos+1)) { 505 /* pull snippets from the different words & fuse */ 506 skip_node->skip_addr = key[KEY_BIT2IDX(msbpos+1)] & MASK((msbpos+1) % _NUM_WORD_BITS_); 507 skip_node->skip_addr = SHL(skip_node->skip_addr, 508 skip_node->skip_len - ((msbpos+1) % _NUM_WORD_BITS_), 509 _NUM_WORD_BITS_); 510 skip_node->skip_addr |= SHR(key[KEY_BIT2IDX(lsbpos+1)],(lsbpos % _NUM_WORD_BITS_),_NUM_WORD_BITS_); 511 } else { 512 skip_node->skip_addr = SHR(key[KEY_BIT2IDX(msbpos+1)], (lsbpos % _NUM_WORD_BITS_),_NUM_WORD_BITS_); 513 } 514 515 /* set up the chain of child pointer, first node has no child since "child" was inited to NULL */ 516 if (child) { 517 skip_node->child[bit].child_node = child; 518 } 519 520 /* calculate child pointer for next loop. NOTE: skip_addr has not been masked 521 * so we still have the child bit in the skip_addr here. 522 */ 523 bit = (skip_node->skip_addr & SHL(1, skip_node->skip_len - 1,_MAX_SKIP_LEN_)) ? 1:0; 524 525 /* calculate node type */ 526 if (lsbpos == lsb-1) { 527 /* first node is payload */ 528 skip_node->type = PAYLOAD; 529 } else { 530 /* other nodes are internal nodes */ 531 skip_node->type = INTERNAL; 532 } 533 534 /* all internal nodes will have the same "count" as the payload node */ 535 skip_node->count = count; 536 537 /* advance lsb to next word */ 538 lsbpos += skip_node->skip_len; 539 540 /* calculate bpm of the skip_node */ 541 if (bpm) { 542 if (lsbpos == _MAX_KEY_LEN_) { 543 /* parent node is 0/0, so there is no branch bit here */ 544 skip_node->bpm = _key_get_bits(bpm, lsbpos, skip_node->skip_len, FALSE); 545 } else { 546 skip_node->bpm = _key_get_bits(bpm, lsbpos+1, skip_node->skip_len+1, FALSE); 547 } 548 } 549 550 /* for all child nodes 0/1 is implicitly obsorbed on parent */ 551 if (msbpos != msb-1) { 552 /* msbpos == (msb-1) is only true for the first node */ 553 skip_node->skip_len--; 554 } 555 skip_node->bpm &= MASK(skip_node->skip_len + 1); 556 skip_node->skip_addr &= MASK(skip_node->skip_len); 557 child = skip_node; 558 } 559 } else { 560 /* skip_len == 0 case, create a payload node with skip_len = 0 and bpm should be 1 bits only 561 * bit 0 and bit "skip_len" are same bit (bit 0). 562 */ 563 skip_node = payload; 564 sal_memset(skip_node, 0, sizeof(trie_node_t)); 565 skip_node->type = PAYLOAD; 566 skip_node->count = count; 567 if (bpm) { 568 skip_node->bpm = _key_get_bits(bpm,1,1,TRUE); 569 } 570 } 571 572 *node = skip_node; 573 return SOC_E_NONE; 574 } 575 576 int _trie_v6_insert(trie_node_t *trie, 577 unsigned int *key, 578 /* bpm bit map if bpm management is required, passing null skips bpm management */ 579 unsigned int *bpm, 580 unsigned int length, 581 trie_node_t *payload, /* payload node */ 582 trie_node_t **child, /* child pointer if the child is modified */ 583 int child_count) 584 { 585 unsigned int lcp; 586 int rv=SOC_E_NONE, bit=0; 587 trie_node_t *node = NULL; 588 589 if (!trie || (length && trie->skip_len && !key) || 590 !payload || !child || (length > _MAX_KEY_LEN_)) return SOC_E_PARAM; 591 592 *child = NULL; 593 594 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 595 596 /* insert cases: 597 * 1 - new key could be the parent of existing node 598 * 2 - new node could become the child of a existing node 599 * 3 - internal node could be inserted and the key becomes one of child 600 * 4 - internal node is converted to a payload node */ 601 602 /* if the new key qualifies as new root do the inserts here */ 603 if (lcp == length) { /* guaranteed: length < _MAX_SKIP_LEN_ */ 604 if (trie->skip_len == lcp) { 605 if (trie->type != INTERNAL) { 606 /* duplicate */ 607 return SOC_E_EXISTS; 608 } else { 609 /* change the internal node to payload node */ 610 _CLONE_TRIE_NODE_(payload,trie); 611 sal_free(trie); 612 payload->type = PAYLOAD; 613 payload->count += child_count; 614 *child = payload; 615 616 if (bpm) { 617 /* bpm at this internal mode must be same as the inserted pivot */ 618 payload->bpm |= _key_get_bits(bpm, lcp+1, lcp+1, FALSE); 619 /* implicity preserve the previous bpm & set bit 0 -myself bit */ 620 } 621 return SOC_E_NONE; 622 } 623 } else { /* skip length can never be less than lcp implcitly here */ 624 /* this node is new parent for the old trie node */ 625 /* lcp is the new skip length */ 626 _CLONE_TRIE_NODE_(payload,trie); 627 *child = payload; 628 629 bit = (trie->skip_addr & SHL(1,trie->skip_len - length - 1,_MAX_SKIP_LEN_)) ? 1 : 0; 630 trie->skip_addr &= MASK(trie->skip_len - length - 1); 631 trie->skip_len -= (length + 1); 632 633 if (bpm) { 634 trie->bpm &= MASK(trie->skip_len+1); 635 } 636 637 payload->skip_addr = (length > 0) ? key[KEY_BIT2IDX(length)] : 0; 638 payload->skip_addr &= MASK(length); 639 payload->skip_len = length; 640 payload->child[bit].child_node = trie; 641 payload->child[!bit].child_node = NULL; 642 payload->type = PAYLOAD; 643 payload->count += child_count; 644 645 if (bpm) { 646 payload->bpm = SHR(payload->bpm, trie->skip_len + 1,_NUM_WORD_BITS_); 647 payload->bpm |= _key_get_bits(bpm, payload->skip_len+1, payload->skip_len+1, FALSE); 648 } 649 } 650 } else if (lcp == trie->skip_len) { 651 /* key length is implictly greater than lcp here */ 652 /* decide based on key's next applicable bit */ 653 bit = (key[KEY_BIT2IDX(length-lcp)] & 654 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 655 656 if (!trie->child[bit].child_node) { 657 /* the key is going to be one of the child of existing node */ 658 /* should be the child */ 659 rv = _trie_v6_skip_node_alloc(&node, key, bpm, 660 length-lcp-1, /* 0 based msbit position */ 661 length-lcp-1, 662 payload, child_count); 663 if (SOC_SUCCESS(rv)) { 664 trie->child[bit].child_node = node; 665 trie->count += child_count; 666 } else { 667 LOG_CLI((BSL_META("\n Error on trie skip node allocaiton [%d]!!!!\n"), 668 rv)); 669 } 670 } else { 671 rv = _trie_v6_insert(trie->child[bit].child_node, 672 key, bpm, length - lcp - 1, 673 payload, child, child_count); 674 if (SOC_SUCCESS(rv)) { 675 trie->count += child_count; 676 if (*child != NULL) { /* chande the old child pointer to new child */ 677 trie->child[bit].child_node = *child; 678 *child = NULL; 679 } 680 } 681 } 682 } else { 683 trie_node_t *newchild = NULL; 684 685 /* need to introduce internal nodes */ 686 node = sal_alloc(sizeof(trie_node_t), "trie-node"); 687 _CLONE_TRIE_NODE_(node, trie); 688 689 rv = _trie_v6_skip_node_alloc(&newchild, key, bpm, 690 ((lcp)?length-lcp-1:length-1), 691 length - lcp - 1, 692 payload, child_count); 693 if (SOC_SUCCESS(rv)) { 694 bit = (key[KEY_BIT2IDX(length-lcp)] & 695 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1: 0; 696 697 node->child[!bit].child_node = trie; 698 node->child[bit].child_node = newchild; 699 node->type = INTERNAL; 700 node->skip_addr = SHR(trie->skip_addr,trie->skip_len - lcp,_MAX_SKIP_LEN_); 701 node->skip_len = lcp; 702 node->count += child_count; 703 if (bpm) { 704 node->bpm = SHR(node->bpm, trie->skip_len - lcp, _MAX_SKIP_LEN_); 705 } 706 *child = node; 707 708 trie->skip_addr &= MASK(trie->skip_len - lcp - 1); 709 trie->skip_len -= (lcp + 1); 710 if (bpm) { 711 trie->bpm &= MASK(trie->skip_len+1); 712 } 713 } else { 714 LOG_CLI((BSL_META("\n Error on trie skip node allocaiton [%d]!!!!\n"), rv)); 715 sal_free(node); 716 } 717 } 718 719 return rv; 720 } 721 722 int _trie_v6_delete(trie_node_t *trie, 723 unsigned int *key, 724 unsigned int length, 725 trie_node_t **payload, 726 trie_node_t **child) 727 { 728 unsigned int lcp; 729 int rv=SOC_E_NONE, bit=0; 730 trie_node_t *node = NULL; 731 732 /* our algorithm should return before the length < 0, so this means 733 * something wrong with the trie structure. Internal error? 734 */ 735 if (!trie || (length && trie->skip_len && !key) || 736 !payload || !child || (length > _MAX_KEY_LEN_)) { 737 return SOC_E_PARAM; 738 } 739 740 *child = NULL; 741 742 /* check a section of key, return the number of matched bits and value of next bit */ 743 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 744 745 if (length > trie->skip_len) { 746 747 if (lcp == trie->skip_len) { 748 749 bit = (key[KEY_BIT2IDX(length-lcp)] & 750 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 751 752 /* based on next bit branch left or right */ 753 if (trie->child[bit].child_node) { 754 755 /* has child node, keep searching */ 756 rv = _trie_v6_delete(trie->child[bit].child_node, key, length - lcp - 1, payload, child); 757 758 if (rv == SOC_E_BUSY) { 759 760 trie->child[bit].child_node = NULL; /* sal_free the child */ 761 rv = SOC_E_NONE; 762 trie->count--; 763 764 if (trie->type == INTERNAL) { 765 766 bit = (bit==0)?1:0; 767 768 if (trie->child[bit].child_node == NULL) { 769 /* parent and child connected, sal_free the middle-node itself */ 770 sal_free(trie); 771 rv = SOC_E_BUSY; 772 } else { 773 /* fuse the parent & child */ 774 if (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= 775 _MAX_SKIP_LEN_) { 776 *child = trie->child[bit].child_node; 777 rv = _trie_fuse_child(trie, bit); 778 if (rv != SOC_E_NONE) { 779 *child = NULL; 780 } 781 } 782 } 783 } 784 } else if (SOC_SUCCESS(rv)) { 785 trie->count--; 786 /* update child pointer if applicable */ 787 if (*child != NULL) { 788 trie->child[bit].child_node = *child; 789 *child = NULL; 790 } 791 } 792 } else { 793 /* no child node case 0: not found */ 794 rv = SOC_E_NOT_FOUND; 795 } 796 797 } else { 798 /* some bits are not matching, case 0: not found */ 799 rv = SOC_E_NOT_FOUND; 800 } 801 } else if (length == trie->skip_len) { 802 /* when length equal to skip_len, unless this is a payload node 803 * and it's an exact match (lcp == length), we can not found a match 804 */ 805 if (!((lcp == length) && (trie->type == PAYLOAD))) { 806 rv = SOC_E_NOT_FOUND; 807 } else { 808 /* payload node can be deleted */ 809 /* if this node has 2 children update it to internal node */ 810 rv = SOC_E_NONE; 811 812 if (trie->child[0].child_node && trie->child[1].child_node ) { 813 /* the node has 2 children, update it to internal node */ 814 _BITCLR(trie->bpm, 0); 815 node = sal_alloc(sizeof(trie_node_t), "trie_node"); 816 _CLONE_TRIE_NODE_(node, trie); 817 node->type = INTERNAL; 818 node->count--; 819 *child = node; 820 } else if (trie->child[0].child_node || trie->child[1].child_node ) { 821 /* if this node has 1 children fuse the children with this node */ 822 bit = (trie->child[0].child_node) ? 0:1; 823 trie->count--; 824 if (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= _MAX_SKIP_LEN_) { 825 /* we need to clear the bpm bit of itself before fusing with child */ 826 _BITCLR(trie->bpm, 0); 827 828 /* able to fuse the node with its child node */ 829 *child = trie->child[bit].child_node; 830 rv = _trie_fuse_child(trie, bit); 831 if (rv != SOC_E_NONE) { 832 *child = NULL; 833 } 834 } else { 835 /* convert it to internal node, we need to alloc new memory for internal nodes 836 * since the old payload node memory will be freed by caller 837 */ 838 /* we need to clear the bpm bit of itself before converting */ 839 _BITCLR(trie->bpm, 0); 840 841 node = sal_alloc(sizeof(trie_node_t), "trie_node"); 842 _CLONE_TRIE_NODE_(node, trie); 843 node->type = INTERNAL; 844 *child = node; 845 } 846 } else { 847 rv = SOC_E_BUSY; 848 } 849 850 *payload = trie; 851 } 852 } else { 853 /* key length is shorter, no match if it's internal node, 854 * will not exact match even if this is a payload node 855 */ 856 rv = SOC_E_NOT_FOUND; /* case 0: not found */ 857 } 858 859 return rv; 860 } 861 862 STATIC INLINE int 863 _trie_v6_splitable(trie_node_t *trie, trie_node_t *child, int max_count, int max_split_count) 864 { 865 /* 866 * NOTE: 867 * ABS(trie->count * 2 - max_count) actually means 868 * ABS(trie->count - (max_count - trie->count)) 869 * which means the count's distance to half depth of the bucket 870 */ 871 int do_split = 0; 872 int half_count = (max_count + 1) >> 1; 873 874 if (trie->count <= max_split_count && trie->count != max_count) { 875 if (child == NULL) { 876 do_split = 1; 877 } else if (trie->count >= half_count && child->count < half_count) { 878 do_split = 1; 879 } else if (trie->count == half_count && child->count == half_count) { 880 do_split = 1; 881 } else if (ABS(child->count * 2 - max_count) > 882 ABS(trie->count * 2 - max_count)) { 883 do_split = 1; 884 } 885 } 886 887 return do_split; 888 } 889 890 /* 891 * Function: 892 * trie_v6_split 893 * Purpose: 894 * Split the trie into 2 based on optimum pivot 895 * NOTE: 896 * max_split_len -- split will make sure the split point 897 * has a length shorter or equal to the max_split_len 898 * unless this will cause a no-split (all prefixs 899 * stays below the split point) 900 * split_to_pair -- used only when the split point will be 901 * used to create a pair of tries later (i.e: dbucket 902 * pair. we assume the split point itself will always be 903 * put into 0* trie if itself is a payload/prefix) 904 */ 905 int _trie_v6_split(trie_node_t *trie, 906 unsigned int *pivot, 907 unsigned int *length, 908 unsigned int *split_count, 909 trie_node_t **split_node, 910 trie_node_t **child, 911 const unsigned int max_count, 912 const unsigned int max_split_len, 913 const int split_to_pair, 914 unsigned int *bpm, 915 trie_split_states_e_t *state, 916 int max_split_count) 917 { 918 int bit=0, rv=SOC_E_NONE; 919 920 if (!trie || !pivot || !length || !split_node || max_count == 0 || !state || max_split_count == 0) return SOC_E_PARAM; 921 922 if (trie->child[0].child_node && trie->child[1].child_node) { 923 bit = (trie->child[0].child_node->count > 924 trie->child[1].child_node->count) ? 0:1; 925 } else { 926 bit = (trie->child[0].child_node)?0:1; 927 } 928 929 /* start building the pivot */ 930 rv = _key_append(pivot, length, trie->skip_addr, trie->skip_len); 931 if (SOC_FAILURE(rv)) return rv; 932 933 if (bpm) { 934 unsigned int scratch=0; 935 rv = _bpm_append(bpm, &scratch, trie->bpm, trie->skip_len+1); 936 if (SOC_FAILURE(rv)) return rv; 937 } 938 939 { 940 /* 941 * split logic to make sure the split length is shorter than the 942 * requested max_split_len, unless we don't actully split the 943 * tree if we stop here. 944 * if (*length > max_split_len) && (trie->count != max_count) { 945 * need to split at or above this node. might need to split the node in middle 946 * } else if ((ABS(child count*2 - max_count) > ABS(count*2 - max_count)) || 947 * ((*length == max_split_len) && (trie->count != max_count))) { 948 * (the check above imply trie->count != max_count, so also imply *length < max_split_len) 949 * need to split at this node. 950 * } else { 951 * keep searching, will be better split at longer pivot. 952 * } 953 */ 954 if ((*length > max_split_len) && (trie->count != max_count)) { 955 /* the pivot is getting too long, we better split at this node for 956 * better bucket capacity efficiency if we can. We can split if 957 * the trie node has a count != max_count, which means the 958 * resulted new trie will not have all pivots (FULL) 959 */ 960 if ((TRIE_SPLIT_STATE_PAYLOAD_SPLIT == *state) && 961 (trie->type == INTERNAL)) { 962 *state = TRIE_SPLIT_STATE_PAYLOAD_SPLIT_DONE; 963 } else { 964 if (((*length - max_split_len) > trie->skip_len) && (trie->skip_len == 0)) { 965 /* the length is longer than max_split_len, and the trie->skip_len is 0, 966 * so the best we can do is use the node as the split point 967 */ 968 *split_node = trie; 969 *split_count = trie->count; 970 971 *state = TRIE_SPLIT_STATE_PRUNE_NODES; 972 return rv; 973 } 974 975 /* we need to insert a node and use it as split point */ 976 *split_node = sal_alloc(sizeof(trie_node_t), "trie_node"); 977 sal_memset((*split_node), 0, sizeof(trie_node_t)); 978 (*split_node)->type = INTERNAL; 979 (*split_node)->count = trie->count; 980 981 if ((*length - max_split_len) > trie->skip_len) { 982 /* the length is longer than the max_split_len, and the trie->skip_len is 983 * shorter than the difference (max_split_len pivot is not covered by this 984 * node but covered by its parent, the best we can do is split at the branch 985 * lead to this node. we insert a skip_len=0 node and use it as split point 986 */ 987 (*split_node)->skip_len = 0; 988 (*split_node)->skip_addr = 0; 989 (*split_node)->bpm = (trie->bpm >> trie->skip_len); 990 991 if (_BITGET(trie->skip_addr, (trie->skip_len-1))) { 992 (*split_node)->child[1].child_node = trie; 993 } else { 994 (*split_node)->child[0].child_node = trie; 995 } 996 997 /* the split point is with length max_split_len */ 998 *length -= trie->skip_len; 999 1000 /* update the current node to reflect the node inserted */ 1001 trie->skip_len = trie->skip_len - 1; 1002 } else { 1003 /* the length is longer than the max_split_len, and the trie->skip_len is 1004 * longer than the difference (max_split_len pivot is covered by this 1005 * node, we insert a node with length = max_split_len and use it as split point 1006 */ 1007 (*split_node)->skip_len = trie->skip_len - (*length - max_split_len); 1008 (*split_node)->skip_addr = (trie->skip_addr >> (*length - max_split_len)); 1009 (*split_node)->bpm = (trie->bpm >> (*length - max_split_len)); 1010 1011 if (_BITGET(trie->skip_addr, (*length-max_split_len-1))) { 1012 (*split_node)->child[1].child_node = trie; 1013 } else { 1014 (*split_node)->child[0].child_node = trie; 1015 } 1016 1017 /* update the current node to reflect the node inserted */ 1018 trie->skip_len = *length - max_split_len - 1; 1019 1020 /* the split point is with length max_split_len */ 1021 *length = max_split_len; 1022 } 1023 1024 trie->skip_addr = trie->skip_addr & BITMASK(trie->skip_len); 1025 trie->bpm = trie->bpm & BITMASK(trie->skip_len + 1); 1026 1027 /* there is no need to update the parent node's child_node pointer 1028 * to the "trie" node since we will split here and the parent node's 1029 * child_node pointer will be set to NULL later 1030 */ 1031 *split_count = trie->count; 1032 if (bpm) { 1033 rv = taps_key_shift(_MAX_KEY_LEN_, bpm, _MAX_KEY_LEN_, trie->skip_len+1); 1034 } 1035 1036 if (SOC_SUCCESS(rv)) { 1037 rv = taps_key_shift(_MAX_KEY_LEN_, pivot, *length+trie->skip_len+1, trie->skip_len+1); 1038 } 1039 *state = TRIE_SPLIT_STATE_PRUNE_NODES; 1040 return rv; 1041 } 1042 } else if ( ((*length == max_split_len) && (trie->count != max_count) && (trie->count <= max_split_count)) || 1043 _trie_v6_splitable(trie, trie->child[bit].child_node, max_count, max_split_count)) { 1044 /* 1045 * (1) when the node is at the max_split_len and if used as spliting point 1046 * the resulted trie will not have all pivots (FULL). we should split 1047 * at this node. 1048 * (2) when the node is at the max_split_len and if the resulted trie 1049 * will have all pivots (FULL), we fall through to keep searching 1050 * (3) when the node is shorter than the max_split_len and the node 1051 * has a more even pivot distribution compare to it's cc, we 1052 * can split at this node. The split count must be less than or 1053 * equal to max_split_count. 1054 * (4) when the node's count is only 1, we must split at this point. 1055 * 1056 * NOTE: 1057 * when trie->count == max_count, the above check will be FALSE 1058 * so here it guarrantees *length < max_split_len. We don't 1059 * need to further split this node. 1060 */ 1061 *split_node = trie; 1062 *split_count = trie->count; 1063 1064 if ((TRIE_SPLIT_STATE_PAYLOAD_SPLIT == *state) && 1065 (trie->type == INTERNAL)) { 1066 *state = TRIE_SPLIT_STATE_PAYLOAD_SPLIT_DONE; 1067 } else { 1068 *state = TRIE_SPLIT_STATE_PRUNE_NODES; 1069 return rv; 1070 } 1071 } else { 1072 /* we can not split at this node, keep searching, it's better to 1073 * split at longer pivot 1074 */ 1075 rv = _key_append(pivot, length, bit, 1); 1076 if (SOC_FAILURE(rv)) return rv; 1077 1078 rv = _trie_v6_split(trie->child[bit].child_node, 1079 pivot, length, 1080 split_count, split_node, 1081 child, max_count, max_split_len, 1082 split_to_pair, bpm, state, max_split_count); 1083 } 1084 } 1085 1086 /* free up internal nodes if applicable */ 1087 switch(*state) { 1088 case TRIE_SPLIT_STATE_PAYLOAD_SPLIT_DONE: 1089 if (trie->type == PAYLOAD) { 1090 *state = TRIE_SPLIT_STATE_PRUNE_NODES; 1091 *split_node = trie; 1092 *split_count = trie->count; 1093 } else { 1094 /* shift the pivot to right to ignore this internal node */ 1095 rv = taps_key_shift(_MAX_KEY_LEN_, pivot, *length, trie->skip_len+1); 1096 assert(*length >= trie->skip_len + 1); 1097 *length -= (trie->skip_len + 1); 1098 } 1099 break; 1100 1101 case TRIE_SPLIT_STATE_PRUNE_NODES: 1102 if (trie->count == *split_count) { 1103 /* if the split point has associate internal nodes they have to 1104 * be cleaned up */ 1105 assert(trie->type == INTERNAL); 1106 assert(!(trie->child[0].child_node && trie->child[1].child_node)); 1107 sal_free(trie); 1108 } else { 1109 assert(*child == NULL); 1110 /* fuse with child if possible */ 1111 trie->child[bit].child_node = NULL; 1112 bit = (bit==0)?1:0; 1113 trie->count -= *split_count; 1114 1115 /* optimize more */ 1116 if ((trie->type == INTERNAL) && 1117 (trie->skip_len + 1118 trie->child[bit].child_node->skip_len + 1 <= _MAX_SKIP_LEN_)) { 1119 *child = trie->child[bit].child_node; 1120 rv = _trie_fuse_child(trie, bit); 1121 if (rv != SOC_E_NONE) { 1122 *child = NULL; 1123 } 1124 } 1125 *state = TRIE_SPLIT_STATE_DONE; 1126 } 1127 break; 1128 1129 case TRIE_SPLIT_STATE_DONE: 1130 /* adjust parent's count */ 1131 assert(*split_count > 0); 1132 assert(trie->count >= *split_count); 1133 1134 /* update the child pointer if child was pruned */ 1135 if (*child != NULL) { 1136 trie->child[bit].child_node = *child; 1137 *child = NULL; 1138 } 1139 trie->count -= *split_count; 1140 break; 1141 1142 default: 1143 break; 1144 } 1145 1146 return rv; 1147 } 1148 1149 1150 1151 /* 1152 * Function: 1153 * _trie_v6_merge 1154 * Purpose: 1155 * merge or fuse the child trie with parent trie 1156 */ 1157 int 1158 _trie_v6_merge(trie_node_t *parent_trie, 1159 trie_node_t *child_trie, 1160 unsigned int *pivot, 1161 unsigned int length, 1162 trie_node_t **new_parent) 1163 { 1164 int rv, child_count; 1165 trie_node_t *child = NULL, clone; 1166 unsigned int bpm[TAPS_MAX_KEY_SIZE_WORDS] = {0}; 1167 unsigned int child_pivot[BITS2WORDS(_MAX_KEY_LEN_)] = {0}; 1168 unsigned int child_length = 0; 1169 1170 if (!parent_trie || length == 0 || !pivot || !new_parent || (length > _MAX_KEY_LEN_)) 1171 return SOC_E_PARAM; 1172 1173 /* 1174 * to do merge, there is one and only one condition: 1175 * parent must cover the child 1176 */ 1177 1178 /* 1179 * child pivot could be an internal node, i.e., NOT_FOUND on search 1180 * so check the out child instead of rv. 1181 */ 1182 _trie_v6_search(child_trie, pivot, length, &child, child_pivot, &child_length, 0, 1); 1183 if (child == NULL) { 1184 return SOC_E_PARAM; 1185 } 1186 1187 _CLONE_TRIE_NODE_(&clone, child); 1188 1189 if (child->type == PAYLOAD && child->bpm) { 1190 _TAPS_SET_KEY_BIT(bpm, 0, TAPS_IPV6_KEY_SIZE); 1191 } 1192 1193 if (child != child_trie) { 1194 rv = _trie_v6_skip_node_free(child_trie, child_pivot, child_length); 1195 if (rv < 0) { 1196 return SOC_E_PARAM; 1197 } 1198 } 1199 1200 /* Record the child count before being cleared */ 1201 child_count = child->count; 1202 1203 /* Clear the info before insert, mainly it is to prevent previous non-zero 1204 * count being erroneously included to calculation. 1205 */ 1206 sal_memset(child, 0, sizeof(*child)); 1207 /* merge happens on bucket trie, which usually does not need bpm */ 1208 rv = _trie_v6_insert(parent_trie, child_pivot, bpm, child_length, child, 1209 new_parent, child_count); 1210 if (rv < 0) { 1211 return SOC_E_PARAM; 1212 } 1213 1214 /* 1215 * child node, the inserted node, will be modified during insert, 1216 * and it must be a leaf node of the parent trie without any child. 1217 * The child node could be either payload or internal. 1218 */ 1219 if (child->child[0].child_node || child->child[1].child_node) { 1220 return SOC_E_PARAM; 1221 } 1222 if (clone.type == INTERNAL) { 1223 child->type = INTERNAL; 1224 } 1225 child->child[0].child_node = clone.child[0].child_node; 1226 child->child[1].child_node = clone.child[1].child_node; 1227 1228 return SOC_E_NONE; 1229 } 1230 1231 1232 1233 1234 /* 1235 * Function: 1236 * trie_split 1237 * Purpose: 1238 * Split the trie into 2 such that the new sub trie covers given prefix/length. 1239 * NOTE: 1240 * key, key_len -- The given prefix/length 1241 * max_split_count -- The sub trie's max allowed count. 1242 */ 1243 int 1244 _trie_v6_split2(trie_node_t *trie, 1245 unsigned int *key, 1246 unsigned int key_len, 1247 unsigned int *pivot, 1248 unsigned int *pivot_len, 1249 unsigned int *split_count, 1250 trie_node_t **split_node, 1251 trie_node_t **child, 1252 trie_split2_states_e_t *state, 1253 const int max_split_count, 1254 const int exact_same) 1255 { 1256 unsigned int lcp=0; 1257 int bit=0, rv=SOC_E_NONE; 1258 1259 if (!trie || !pivot || !pivot_len || !split_node || !state || max_split_count == 0) return SOC_E_PARAM; 1260 /* start building the pivot */ 1261 rv = _key_append(pivot, pivot_len, trie->skip_addr, trie->skip_len); 1262 if (SOC_FAILURE(rv)) return rv; 1263 1264 1265 lcp = lcplen(key, key_len, trie->skip_addr, trie->skip_len); 1266 1267 if (lcp == trie->skip_len) { 1268 if (trie->count <= max_split_count && 1269 (!exact_same || (key_len - lcp) == 0)) { 1270 *split_node = trie; 1271 *split_count = trie->count; 1272 if (trie->count < max_split_count) { 1273 *state = TRIE_SPLIT2_STATE_PRUNE_NODES; 1274 } 1275 return SOC_E_NONE; 1276 } 1277 if (key_len > lcp) { 1278 bit = (key[KEY_BIT2IDX(key_len - lcp)] & \ 1279 (1 << ((key_len - lcp - 1) % _NUM_WORD_BITS_))) ? 1:0; 1280 1281 /* based on next bit branch left or right */ 1282 if (trie->child[bit].child_node) { 1283 /* we can not split at this node, keep searching, it's better to 1284 * split at longer pivot 1285 */ 1286 rv = _key_append(pivot, pivot_len, bit, 1); 1287 if (SOC_FAILURE(rv)) return rv; 1288 1289 rv = _trie_v6_split2(trie->child[bit].child_node, 1290 key, key_len - lcp - 1, 1291 pivot, pivot_len, split_count, 1292 split_node, child, state, 1293 max_split_count, exact_same); 1294 if (SOC_FAILURE(rv)) return rv; 1295 } 1296 } 1297 } 1298 1299 /* free up internal nodes if applicable */ 1300 switch(*state) { 1301 case TRIE_SPLIT2_STATE_NONE: /* fail to split */ 1302 break; 1303 1304 case TRIE_SPLIT2_STATE_PRUNE_NODES: 1305 if (trie->count == *split_count) { 1306 /* if the split point has associate internal nodes they have to 1307 * be cleaned up */ 1308 assert(trie->type == INTERNAL); 1309 /* at most one child */ 1310 assert(!(trie->child[0].child_node && trie->child[1].child_node)); 1311 /* at least one child */ 1312 assert(trie->child[0].child_node || trie->child[1].child_node); 1313 sal_free(trie); 1314 } else { 1315 assert(*child == NULL); 1316 /* fuse with child if possible */ 1317 trie->child[bit].child_node = NULL; 1318 bit = (bit==0)?1:0; 1319 trie->count -= *split_count; 1320 1321 /* optimize more */ 1322 if ((trie->type == INTERNAL) && 1323 (trie->skip_len + 1324 trie->child[bit].child_node->skip_len + 1 <= _MAX_SKIP_LEN_)) { 1325 *child = trie->child[bit].child_node; 1326 rv = _trie_fuse_child(trie, bit); 1327 if (rv != SOC_E_NONE) { 1328 *child = NULL; 1329 } 1330 } 1331 *state = TRIE_SPLIT2_STATE_DONE; 1332 } 1333 break; 1334 1335 case TRIE_SPLIT2_STATE_DONE: 1336 /* adjust parent's count */ 1337 assert(*split_count > 0); 1338 assert(trie->count >= *split_count); 1339 1340 /* update the child pointer if child was pruned */ 1341 if (*child != NULL) { 1342 trie->child[bit].child_node = *child; 1343 *child = NULL; 1344 } 1345 trie->count -= *split_count; 1346 break; 1347 1348 default: 1349 break; 1350 } 1351 1352 return rv; 1353 } 1354 1355 1356 1357 /* 1358 * Function: 1359 * _trie_v6_propagate_prefix 1360 * Purpose: 1361 * Propogate prefix BPM. If the propogation starts from intermediate pivot on 1362 * the trie, then the prefix length has to be appropriately adjusted or else 1363 * it will end up with ill updates. 1364 * Assumption: the prefix length is adjusted as per trie node on which is starts from. 1365 * If node == head node then adjust is none 1366 * node == pivot, then prefix length = org len - pivot len 1367 */ 1368 int _trie_v6_propagate_prefix(trie_node_t *trie, 1369 unsigned int *pfx, 1370 unsigned int len, 1371 unsigned int add, /* 0-del/1-add */ 1372 trie_propagate_cb_f cb, 1373 trie_bpm_cb_info_t *cb_info) 1374 { 1375 int rv = SOC_E_NONE; /*, index;*/ 1376 unsigned int bit=0, lcp=0; 1377 1378 if (!trie || (len && trie->skip_len && !pfx) || 1379 (len > _MAX_KEY_LEN_) || !cb || !cb_info) return SOC_E_PARAM; 1380 1381 if (len > 0) { 1382 /* BPM bit maps has to be updated before propagation */ 1383 lcp = lcplen(pfx, len, trie->skip_addr, trie->skip_len); 1384 /* if the lcp is less than prefix length the prefix is not applicable 1385 * for any propagation */ 1386 if (lcp < ((len>trie->skip_len)?trie->skip_len:len)) { 1387 return SOC_E_NONE; 1388 } else { 1389 if (len > trie->skip_len) { 1390 /* fully matched and more bits to check, go down the trie */ 1391 bit = _key_get_bits(pfx, len-lcp, 1, TRUE); 1392 if (!trie->child[bit].child_node) return SOC_E_NONE; 1393 rv = _trie_v6_propagate_prefix(trie->child[bit].child_node, 1394 pfx, len-lcp-1, add, cb, cb_info); 1395 } else { 1396 /* given pfx exactly matched or covers trie node, this is the 1397 * point to propagate. 1398 */ 1399 /* pfx is <= trie skip len */ 1400 if (!add) { /* delete */ 1401 _BITCLR(trie->bpm, trie->skip_len - len); 1402 } 1403 1404 /* update bit map and propagate if applicable: 1405 * there is no longer bpm than this new prefix 1406 */ 1407 if ((trie->bpm & BITMASK(trie->skip_len - len)) == 0) { 1408 rv = _trie_traverse_propagate_prefix(trie, cb, 1409 cb_info, 1410 BITMASK(trie->skip_len - len)); 1411 if (SOC_E_LIMIT == rv) rv = SOC_E_NONE; 1412 } else if (add && _BITGET(trie->bpm, trie->skip_len - len)) { 1413 /* if adding, and bpm of this node is the specified prefix 1414 * also propagate. (this is really update case) 1415 */ 1416 rv = _trie_traverse_propagate_prefix(trie, cb, 1417 cb_info, 1418 BITMASK(trie->skip_len - len)); 1419 if (SOC_E_LIMIT == rv) rv = SOC_E_NONE; 1420 } 1421 1422 if (add && SOC_SUCCESS(rv)) { 1423 /* this is the case where child bit is the new prefix */ 1424 _BITSET(trie->bpm, trie->skip_len - len); 1425 } 1426 } 1427 } 1428 } else { 1429 1430 if (!add) { /* delete */ 1431 _BITCLR(trie->bpm, trie->skip_len); 1432 } 1433 1434 if ((trie->bpm == 0) || 1435 (add && ((trie->bpm & BITMASK(trie->skip_len)) == 0))) { 1436 /* if adding, and bpm of this node is the specified prefix 1437 * also propagate. (this is really update case) 1438 */ 1439 rv = _trie_traverse_propagate_prefix(trie, cb, cb_info, BITMASK(trie->skip_len)); 1440 if (SOC_E_LIMIT == rv) rv = SOC_E_NONE; 1441 } 1442 1443 if (add && SOC_SUCCESS(rv)) { /* add */ 1444 /* this is the case where child bit is the new prefix */ 1445 _BITSET(trie->bpm, trie->skip_len); 1446 } 1447 } 1448 1449 return rv; 1450 } 1451 1452 /* 1453 * Function: 1454 * _trie_v6_propagate_prefix_validate 1455 * Purpose: 1456 * validate that the provided prefix is valid for propagation. 1457 * The added prefix which was member of a shorter pivot's domain 1458 * must never be more specific than another pivot encounter if any 1459 * in the path 1460 */ 1461 STATIC int _trie_v6_propagate_prefix_validate(trie_node_t *trie, 1462 unsigned int *pfx, 1463 unsigned int len) 1464 { 1465 unsigned int lcp=0, bit=0; 1466 1467 if (!trie || (len && trie->skip_len && !pfx)) return SOC_E_PARAM; 1468 1469 if (len == 0) return SOC_E_NONE; 1470 1471 lcp = lcplen(pfx, len, trie->skip_addr, trie->skip_len); 1472 1473 if (lcp == trie->skip_len) { 1474 if (PAYLOAD == trie->type) { 1475 return SOC_E_PARAM; 1476 } 1477 1478 if (len == lcp) { 1479 return SOC_E_NONE; 1480 } 1481 1482 bit = _key_get_bits(pfx, len-lcp, 1, TRUE); 1483 if (!trie->child[bit].child_node) { 1484 return SOC_E_NONE; 1485 } 1486 1487 return _trie_v6_propagate_prefix_validate(trie->child[bit].child_node, 1488 pfx, len-1-lcp); 1489 } 1490 1491 return SOC_E_NONE; 1492 } 1493 1494 int trie_v6_pivot_propagate_prefix(trie_node_t *pivot, 1495 unsigned int pivot_len, 1496 unsigned int *pfx, 1497 unsigned int len, 1498 unsigned int add, /* 0-del/1-add */ 1499 trie_propagate_cb_f cb, 1500 trie_bpm_cb_info_t *cb_info) 1501 { 1502 int rv = SOC_E_NONE; 1503 1504 if (!pfx || !pivot || (len > _MAX_KEY_LEN_) || 1505 (pivot_len > _MAX_KEY_LEN_) || (len < pivot_len) || 1506 (pivot->type != PAYLOAD) || !cb || !cb_info || 1507 !cb_info->pfx) { 1508 return SOC_E_PARAM; 1509 } 1510 1511 _trie_init_propagate_info(pfx,len,cb,cb_info); 1512 len -= pivot_len; 1513 1514 if (len > 0) { 1515 unsigned int bit = _key_get_bits(pfx, len, 1, 0); 1516 1517 if (pivot->child[bit].child_node) { 1518 /* validate if the pivot provided is correct */ 1519 rv = _trie_v6_propagate_prefix_validate(pivot->child[bit].child_node, 1520 pfx, len-1); 1521 if (SOC_SUCCESS(rv)) { 1522 rv = _trie_v6_propagate_prefix(pivot->child[bit].child_node, 1523 pfx, len-1, 1524 add, cb, cb_info); 1525 } 1526 } /* else nop, nothing to propagate on this path end */ 1527 } else { 1528 /* pivot == prefix */ 1529 rv = _trie_v6_propagate_prefix(pivot, pfx, pivot->skip_len, 1530 add, cb, cb_info); 1531 } 1532 1533 return rv; 1534 } 1535 1536 /* 1537 * Function: 1538 * _pvt_trie_v6_propagate_prefix 1539 * Purpose: 1540 * If the propogation starts from intermediate pivot on 1541 * the trie, then the prefix length has to be appropriately adjusted or else 1542 * it will end up with ill updates. 1543 * Assumption: the prefix length is adjusted as per trie node on 1544 * which is starts from. 1545 * If node == head node then adjust is none 1546 * node == pivot, then prefix length = org len - pivot len 1547 */ 1548 int _pvt_trie_v6_propagate_prefix(trie_node_t *trie, 1549 unsigned int *pfx, 1550 unsigned int len, 1551 trie_propagate_cb_f cb, 1552 trie_bpm_cb_info_t *cb_info) 1553 { 1554 int rv = SOC_E_NONE; 1555 unsigned int bit=0, lcp=0; 1556 1557 if (!trie || (len && trie->skip_len && !pfx) || 1558 (len > _MAX_KEY_LEN_) || !cb || !cb_info) { 1559 return SOC_E_PARAM; 1560 } 1561 1562 if (len > 0) { 1563 lcp = lcplen(pfx, len, trie->skip_addr, trie->skip_len); 1564 /* if the lcp is less than prefix length the prefix is not applicable 1565 * for any propagation */ 1566 if (lcp < ((len>trie->skip_len) ? trie->skip_len : len)) { 1567 return SOC_E_NONE; 1568 } else { 1569 if (len > trie->skip_len) { 1570 bit = _key_get_bits(pfx, len-lcp, 1, TRUE); 1571 if (!trie->child[bit].child_node) { 1572 return SOC_E_NONE; 1573 } 1574 rv = _pvt_trie_v6_propagate_prefix(trie->child[bit].child_node, 1575 pfx, len-lcp-1, cb, cb_info); 1576 } else { 1577 /* pfx is <= trie skip len */ 1578 rv = _pvt_trie_traverse_propagate_prefix(trie, cb, cb_info); 1579 if (SOC_E_LIMIT == rv) { 1580 rv = SOC_E_NONE; 1581 } 1582 } 1583 } 1584 } else { 1585 rv = _pvt_trie_traverse_propagate_prefix(trie, cb, cb_info); 1586 if (SOC_E_LIMIT == rv) { 1587 rv = SOC_E_NONE; 1588 } 1589 } 1590 1591 return rv; 1592 } 1593 1594 /* 1595 * Function: 1596 * pvt_trie_v6_propagate_prefix 1597 * Purpose: 1598 * Propogate prefix from a given pivot. 1599 * Callback function to decide INSERT/DELETE propagation, 1600 * and decide to update bpm_len or not. 1601 */ 1602 int pvt_trie_v6_propagate_prefix(trie_node_t *pivot, 1603 unsigned int pivot_len, 1604 unsigned int *pfx, 1605 unsigned int len, 1606 trie_propagate_cb_f cb, 1607 trie_bpm_cb_info_t *cb_info) 1608 { 1609 int rv = SOC_E_NONE; 1610 1611 if (!pfx || !pivot || (len > _MAX_KEY_LEN_) || 1612 (pivot_len > _MAX_KEY_LEN_) || (len < pivot_len) || 1613 (pivot->type != PAYLOAD) || !cb || !cb_info || 1614 !cb_info->pfx) { 1615 return SOC_E_PARAM; 1616 } 1617 1618 len -= pivot_len; 1619 1620 if (len > 0) { 1621 unsigned int bit = _key_get_bits(pfx, len, 1, 0); 1622 1623 if (pivot->child[bit].child_node) { 1624 /* validate if the pivot provided is correct */ 1625 rv = _trie_v6_propagate_prefix_validate( 1626 pivot->child[bit].child_node, pfx, len-1); 1627 if (SOC_SUCCESS(rv)) { 1628 rv = _pvt_trie_v6_propagate_prefix( 1629 pivot->child[bit].child_node, 1630 pfx, len-1, cb, cb_info); 1631 } 1632 } /* else nop, nothing to propagate on this path end */ 1633 } else { 1634 /* pivot == prefix */ 1635 rv = _pvt_trie_v6_propagate_prefix( 1636 pivot, pfx, pivot->skip_len, cb, cb_info); 1637 } 1638 1639 return rv; 1640 } 1641 1642 /****************/ 1643 /** unit tests **/ 1644 /****************/ 1645 #define _NUM_KEY_ (4 * 1024) 1646 #define _VRF_LEN_ 16 1647 /*#define VERBOSE 1648 #define LOG*/ 1649 /* use the followign diag shell command to run this test: 1650 * tr c3sw test=tmu_trie_v6_ut 1651 */ 1652 typedef struct _v6_payload_s { 1653 trie_node_t node; /*trie node */ 1654 dq_t listnode; /* list node */ 1655 union { 1656 trie_t *trie; 1657 trie_node_t pfx_trie_node; 1658 } info; 1659 unsigned int key[BITS2WORDS(_MAX_KEY_LEN_)]; 1660 unsigned int len; 1661 } v6_payload_t; 1662 1663 STATIC int ut_print_payload_node(trie_node_t *payload, void *datum) 1664 { 1665 v6_payload_t *pyld; 1666 1667 if (payload && payload->type == PAYLOAD) { 1668 pyld = TRIE_ELEMENT_GET(v6_payload_t*, payload, node); 1669 LOG_CLI((BSL_META(" key[0x%08x:0x%08x] Length:%d \n"), 1670 pyld->key[0], pyld->key[1], pyld->len)); 1671 } 1672 return SOC_E_NONE; 1673 } 1674 1675 STATIC int ut_print_prefix_payload_node(trie_node_t *payload, void *datum) 1676 { 1677 v6_payload_t *pyld; 1678 1679 if (payload && payload->type == PAYLOAD) { 1680 pyld = TRIE_ELEMENT_GET(v6_payload_t*, payload, info.pfx_trie_node); 1681 taps_show_prefix(_MAX_KEY_LEN_, pyld->key, pyld->len); 1682 } 1683 return SOC_E_NONE; 1684 } 1685 1686 STATIC int ut_check_duplicate(v6_payload_t *pyld, int pyld_vector_size) 1687 { 1688 int i=0; 1689 1690 assert(pyld); 1691 1692 for (i=0; i < pyld_vector_size; i++) { 1693 if (pyld[i].len == pyld[pyld_vector_size].len && 1694 pyld[i].key[0] == pyld[pyld_vector_size].key[0] && 1695 pyld[i].key[1] == pyld[pyld_vector_size].key[1] && 1696 pyld[i].key[2] == pyld[pyld_vector_size].key[2] && 1697 pyld[i].key[3] == pyld[pyld_vector_size].key[3] && 1698 pyld[i].key[4] == pyld[pyld_vector_size].key[4]) { 1699 break; 1700 } 1701 } 1702 1703 return ((i == pyld_vector_size)?0:1); 1704 } 1705 1706 int tmu_trie_v6_split_ut(unsigned int seed) 1707 { 1708 int index, rv = SOC_E_NONE, numkey=0, id=0; 1709 trie_t *trie, *newtrie; 1710 trie_node_t *newroot; 1711 v6_payload_t *pyld = sal_alloc(_NUM_KEY_ * sizeof(v6_payload_t), "unit-test"); 1712 trie_node_t *pyldptr = NULL; 1713 unsigned int pivot[_MAX_KEY_WORDS_], length; 1714 1715 sal_memset(pyld, 0, _NUM_KEY_ * sizeof(v6_payload_t)); 1716 for (id=0; id < 4; id++) { 1717 switch(id) { 1718 case 0: /* 1:1 split */ 1719 pyld[0].key[3] = 0; pyld[0].key[4] = 0x10; pyld[0].len = _VRF_LEN_ + 8; /* v=0 p=0x10000000/8 */ 1720 pyld[1].key[3] = 0; pyld[1].key[4] = 0x1000; pyld[1].len = _VRF_LEN_ + 16; /* v=0 p=0x10000000/16 */ 1721 pyld[2].key[3] = 0; pyld[2].key[4] = 0x100000; pyld[2].len = _VRF_LEN_ + 24; /* v=0 p=0x10000000/24 */ 1722 pyld[3].key[3] = 0; pyld[3].key[4] = 0x10000000; pyld[3].len = _VRF_LEN_ + 32; /* v=0 p=0x10000000/48 */ 1723 numkey = 4; 1724 break; 1725 case 1: /* 1:1 split */ 1726 pyld[0].key[3] = 0; pyld[0].key[4] = 0x10000000; pyld[0].len = _VRF_LEN_ + 32; /* v=0 p=0x10000000/32 */ 1727 pyld[1].key[3] = 0; pyld[1].key[4] = 0x10000001; pyld[1].len = _VRF_LEN_ + 32; /* v=0 p=0x10000001/32 */ 1728 pyld[2].key[3] = 0; pyld[2].key[4] = 0x10000002; pyld[2].len = _VRF_LEN_ + 32; /* v=0 p=0x10000002/32 */ 1729 pyld[3].key[3] = 0; pyld[3].key[4] = 0x10000003; pyld[3].len = _VRF_LEN_ + 32; /* v=0 p=0x10000002/32 */ 1730 pyld[4].key[3] = 0; pyld[4].key[4] = 0x10000004; pyld[4].len = _VRF_LEN_ + 32; /* v=0 p=0x10000002/32 */ 1731 pyld[5].key[3] = 0; pyld[5].key[4] = 0x10000005; pyld[5].len = _VRF_LEN_ + 32; /* v=0 p=0x10000002/32 */ 1732 numkey = 6; 1733 break; 1734 case 2: /* 2:5 split */ 1735 pyld[0].key[3] = 0; pyld[0].key[4] = 0x100; pyld[0].len = _VRF_LEN_ + 12; 1736 pyld[1].key[3] = 0; pyld[1].key[4] = 0x1011; pyld[1].len = _VRF_LEN_ + 16; 1737 pyld[2].key[3] = 0; pyld[2].key[4] = 0x100000; pyld[2].len = _VRF_LEN_ + 24; 1738 pyld[3].key[3] = 0; pyld[3].key[4] = 0x1000000; pyld[3].len = _VRF_LEN_ + 28; 1739 pyld[4].key[3] = 0; pyld[4].key[4] = 0x1001; pyld[4].len = _VRF_LEN_ + 16; 1740 pyld[5].key[3] = 0; pyld[5].key[4] = 0x10011; pyld[5].len = _VRF_LEN_ + 20; 1741 numkey = 6; 1742 break; 1743 1744 case 3: 1745 { 1746 int dup; 1747 1748 if (seed == 0) { 1749 seed = sal_time(); 1750 sal_srand(seed); 1751 } 1752 1753 index = 0; 1754 LOG_CLI((BSL_META("Random test: %d Seed: 0x%x \n"), id, seed)); 1755 do { 1756 do { 1757 pyld[index].len = (unsigned int)sal_rand() % 128; 1758 pyld[index].len += _VRF_LEN_; 1759 1760 pyld[index].key[0] = 0; 1761 pyld[index].key[1] = 0; 1762 pyld[index].key[2] = 0; 1763 pyld[index].key[3] = 0; 1764 if (pyld[index].len > 128) { 1765 pyld[index].key[0] &= MASK(pyld[index].len-128); 1766 pyld[index].key[1] = (unsigned int) sal_rand(); 1767 pyld[index].key[2] = (unsigned int) sal_rand(); 1768 pyld[index].key[3] = (unsigned int) sal_rand(); 1769 pyld[index].key[4] = (unsigned int) sal_rand(); 1770 } else if (pyld[index].len > 96) { 1771 pyld[index].key[1] &= MASK(pyld[index].len-96); 1772 pyld[index].key[2] = (unsigned int) sal_rand(); 1773 pyld[index].key[3] = (unsigned int) sal_rand(); 1774 pyld[index].key[4] = (unsigned int) sal_rand(); 1775 } else if (pyld[index].len > 64) { 1776 pyld[index].key[2] &= MASK(pyld[index].len-64); 1777 pyld[index].key[3] = (unsigned int) sal_rand(); 1778 pyld[index].key[4] = (unsigned int) sal_rand(); 1779 } else if (pyld[index].len > 32) { 1780 pyld[index].key[3] &= MASK(pyld[index].len-32); 1781 pyld[index].key[4] = (unsigned int) sal_rand(); 1782 } else { 1783 pyld[index].key[4] &= MASK(pyld[index].len); 1784 } 1785 1786 dup = ut_check_duplicate(pyld, index); 1787 if (dup) { 1788 LOG_CLI((BSL_META("\n Duplicate at index[%d]:" 1789 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] " 1790 "Retry!!!\n"), 1791 index, pyld[index].key[0], 1792 pyld[index].key[1], pyld[index].key[2], 1793 pyld[index].key[3], pyld[index].key[4])); 1794 } 1795 } while(dup > 0); 1796 } while(++index < _NUM_KEY_); 1797 1798 numkey = index; 1799 } 1800 break; 1801 1802 default: 1803 return SOC_E_PARAM; 1804 } 1805 1806 trie_init(_MAX_KEY_LEN_, &trie); 1807 trie_init(_MAX_KEY_LEN_, &newtrie); 1808 1809 for(index=0; index < numkey && rv == SOC_E_NONE; index++) { 1810 rv = trie_insert(trie, &pyld[index].key[0], NULL, pyld[index].len, &pyld[index].node); 1811 } 1812 1813 rv = trie_split(trie, _MAX_KEY_LEN_, FALSE, pivot, &length, &newroot, NULL, FALSE, 1024); 1814 if (SOC_SUCCESS(rv)) { 1815 LOG_CLI((BSL_META("\n Split Trie Pivot: 0x%08x 0x%08x " 1816 "Length: %d Root: %p \n"), 1817 pivot[0], pivot[1], length, newroot)); 1818 LOG_CLI((BSL_META(" $Payload Count Old Trie:%d New Trie:%d \n"), 1819 trie->trie->count, newroot->count)); 1820 1821 /* set new trie */ 1822 newtrie->trie = newroot; 1823 #ifdef VERBOSE 1824 LOG_CLI((BSL_META("\n OLD Trie Dump ############: \n"))); 1825 trie_dump(trie, NULL, NULL); 1826 LOG_CLI((BSL_META("\n SPLIT Trie Dump ############: \n"))); 1827 trie_dump(newtrie, NULL, NULL); 1828 #endif 1829 1830 for(index=0; index < numkey && rv == SOC_E_NONE; index++) { 1831 rv = trie_search(trie, &pyld[index].key[0], pyld[index].len, &pyldptr); 1832 if (rv != SOC_E_NONE) { 1833 rv = trie_search(newtrie, &pyld[index].key[0], pyld[index].len, &pyldptr); 1834 if (rv != SOC_E_NONE) { 1835 LOG_CLI((BSL_META("SEARCH: Key=0x%x 0x%x 0x%x 0x%x 0x%x " 1836 "len %d SEARCH idx:%d failed on " 1837 "both trie!!!!\n"), 1838 pyld[index].key[0], pyld[index].key[1], 1839 pyld[index].key[2], pyld[index].key[3], 1840 pyld[index].key[4], pyld[index].len, index)); 1841 } else { 1842 assert(pyldptr == &pyld[index].node); 1843 } 1844 } 1845 } 1846 1847 } 1848 } 1849 1850 trie_destroy(trie); 1851 trie_destroy(newtrie); 1852 sal_free(pyld); 1853 return rv; 1854 } 1855 1856 int tmu_taps_trie_v6_ut(int id, unsigned int seed) 1857 { 1858 int index, rv = SOC_E_NONE, numkey=0, num_deleted=0; 1859 trie_t *trie; 1860 v6_payload_t *pyld = sal_alloc(_NUM_KEY_ * sizeof(v6_payload_t), "unit-test"); 1861 trie_node_t *pyldptr = NULL; 1862 unsigned int result_len=0, result_key[_MAX_KEY_WORDS_]; 1863 1864 /* keys packed right to left (ie) most significant word starts at index 0*/ 1865 sal_memset(pyld, 0, _NUM_KEY_ * sizeof(v6_payload_t)); 1866 switch(id) { 1867 case 0: 1868 pyld[0].key[3] = 0; pyld[0].key[4] = 0x10; pyld[0].len = _VRF_LEN_ + 8; /* v=0 p=0x10000000/8 */ 1869 pyld[1].key[3] = 0; pyld[1].key[4] = 0x1000; pyld[1].len = _VRF_LEN_ + 16; /* v=0 p=0x10000000/16 */ 1870 pyld[2].key[3] = 0; pyld[2].key[4] = 0x100000; pyld[2].len = _VRF_LEN_ + 24; /* v=0 p=0x10000000/24 */ 1871 pyld[3].key[3] = 0; pyld[3].key[4] = 0x10000000; pyld[3].len = _VRF_LEN_ + 32; /* v=0 p=0x10000000/48 */ 1872 numkey = 4; 1873 break; 1874 1875 case 1: 1876 pyld[0].key[3] = 0; pyld[0].key[4] = 0x123456; pyld[0].len = _VRF_LEN_ + 24; /* v=0 p=0x12345678/24 */ 1877 pyld[1].key[3] = 0; pyld[1].key[4] = 0x246; pyld[1].len = _VRF_LEN_ + 13; /* v=0 p=0x12345678/13 */ 1878 pyld[2].key[3] = 0; pyld[2].key[4] = 0x24; pyld[2].len = _VRF_LEN_ + 9; /* v=0 p=0x12345678/9 */ 1879 numkey = 3; 1880 break; 1881 1882 case 2: /* dup routes on another vrf */ 1883 pyld[0].key[3] = 0; pyld[0].key[4] = 0x1123456; pyld[0].len = _VRF_LEN_ + 24; /* v=1 p=0x12345678/24 */ 1884 pyld[1].key[3] = 0; pyld[1].key[4] = 0x2246; pyld[1].len = _VRF_LEN_ + 13; /* v=1 p=0x12345678/13 */ 1885 pyld[2].key[3] = 0; pyld[2].key[4] = 0x224; pyld[2].len = _VRF_LEN_ + 9; /* v=1 p=0x12345678/9 */ 1886 numkey = 3; 1887 break; 1888 1889 case 3: 1890 pyld[0].key[3] = 0; pyld[0].key[4] = 0x10000000; pyld[0].len = _VRF_LEN_ + 32; /* v=0 p=0x10000000/32 */ 1891 pyld[1].key[3] = 0; pyld[1].key[4] = 0x10000001; pyld[1].len = _VRF_LEN_ + 32; /* v=0 p=0x10000001/32 */ 1892 pyld[2].key[3] = 0; pyld[2].key[4] = 0x10000002; pyld[2].len = _VRF_LEN_ + 32; /* v=0 p=0x10000002/32 */ 1893 numkey = 3; 1894 break; 1895 1896 case 4: 1897 pyld[0].key[3] = 0; pyld[0].key[4] = 0x12345670; pyld[0].len = _VRF_LEN_ + 32; /* v=0 p=0x12345670/32 */ 1898 pyld[1].key[3] = 0; pyld[1].key[4] = 0x12345671; pyld[1].len = _VRF_LEN_ + 32; /* v=0 p=0x12345671/32 */ 1899 pyld[2].key[3] = 0; pyld[2].key[4] = 0x91a2b38; pyld[2].len = _VRF_LEN_ + 31; /* v=0 p=0x12345670/31 */ 1900 numkey = 3; 1901 break; 1902 1903 case 5: 1904 pyld[0].key[3] = 0; pyld[0].key[4] = 0x20; pyld[0].len = _VRF_LEN_ + 8; /* v=0 p=0x20000000/8 */ 1905 pyld[1].key[3] = 0; pyld[1].key[4] = 0x8000; pyld[1].len = _VRF_LEN_ + 16; /* v=0 p=0x80000000/16 */ 1906 pyld[2].key[3] = 0; pyld[2].key[4] = 0; pyld[2].len = _VRF_LEN_ + 0; /* v=0 p=0/0 */ 1907 numkey = 3; 1908 break; 1909 1910 case 6: 1911 { 1912 int dup; 1913 1914 if (seed == 0) { 1915 seed = sal_time(); 1916 sal_srand(seed); 1917 } 1918 index = 0; 1919 LOG_CLI((BSL_META("Random test: %d Seed: 0x%x \n"), id, seed)); 1920 do { 1921 do { 1922 pyld[index].len = (unsigned int)sal_rand() % 128; 1923 pyld[index].len += _VRF_LEN_; 1924 1925 pyld[index].key[0] = 0; 1926 pyld[index].key[1] = 0; 1927 pyld[index].key[2] = 0; 1928 pyld[index].key[3] = 0; 1929 if (pyld[index].len > 128) { 1930 pyld[index].key[0] &= MASK(pyld[index].len-128); 1931 pyld[index].key[1] = (unsigned int) sal_rand(); 1932 pyld[index].key[2] = (unsigned int) sal_rand(); 1933 pyld[index].key[3] = (unsigned int) sal_rand(); 1934 pyld[index].key[4] = (unsigned int) sal_rand(); 1935 } else if (pyld[index].len > 96) { 1936 pyld[index].key[1] &= MASK(pyld[index].len-96); 1937 pyld[index].key[2] = (unsigned int) sal_rand(); 1938 pyld[index].key[3] = (unsigned int) sal_rand(); 1939 pyld[index].key[4] = (unsigned int) sal_rand(); 1940 } else if (pyld[index].len > 64) { 1941 pyld[index].key[2] &= MASK(pyld[index].len-64); 1942 pyld[index].key[3] = (unsigned int) sal_rand(); 1943 pyld[index].key[4] = (unsigned int) sal_rand(); 1944 } else if (pyld[index].len > 32) { 1945 pyld[index].key[3] &= MASK(pyld[index].len-32); 1946 pyld[index].key[4] = (unsigned int) sal_rand(); 1947 } else { 1948 pyld[index].key[4] &= MASK(pyld[index].len); 1949 } 1950 1951 dup = ut_check_duplicate(pyld, index); 1952 if (dup) { 1953 LOG_CLI((BSL_META("\n Duplicate at index[%d]:" 1954 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] Retry!!!\n"), 1955 index, pyld[index].key[0], 1956 pyld[index].key[1], pyld[index].key[2], 1957 pyld[index].key[3], pyld[index].key[4])); 1958 } 1959 } while(dup > 0); 1960 } while(++index < _NUM_KEY_); 1961 1962 numkey = index; 1963 } 1964 break; 1965 1966 default: 1967 sal_free(pyld); 1968 return -1; 1969 } 1970 1971 trie_init(_MAX_KEY_LEN_, &trie); 1972 LOG_CLI((BSL_META("\n Num keys to test= %d \n"), numkey)); 1973 1974 for(index=0; index < numkey && rv == SOC_E_NONE; index++) { 1975 unsigned int vrf=0, i; 1976 vrf = _key_get_bits(pyld[index].key, pyld[index].len, _VRF_LEN_, FALSE); 1977 1978 #ifdef LOG 1979 LOG_CLI((BSL_META("+ Inserted Key=0x%x 0x%x 0x%x 0x%x 0x%x 0x%x " 1980 "vpn=0x%x Len=%d idx:%d\n"), 1981 pyld[index].key[0], pyld[index].key[1], 1982 pyld[index].key[2], pyld[index].key[3], 1983 pyld[index].key[4], vrf, pyld[index].len, index)); 1984 #endif 1985 rv = trie_insert(trie, &pyld[index].key[0], NULL, pyld[index].len, &pyld[index].node); 1986 if (rv != SOC_E_NONE) { 1987 LOG_CLI((BSL_META("FAILED to Insert Key=0x%x 0x%x 0x%x 0x%x 0x%x " 1988 "vpn=0x%x Len=%d idx:%d\n"), 1989 pyld[index].key[0], pyld[index].key[1], 1990 pyld[index].key[2], pyld[index].key[3], 1991 pyld[index].key[4], vrf, pyld[index].len, index)); 1992 } 1993 #define _VERBOSE_SEARCH_ 1994 /* search all keys & figure out breakage right away */ 1995 for (i=0; i <= index && rv == SOC_E_NONE; i++) { 1996 #ifdef _VERBOSE_SEARCH_ 1997 result_key[0] = 0; 1998 result_key[1] = 0; 1999 result_key[2] = 0; 2000 result_key[3] = 0; 2001 result_key[4] = 0; 2002 result_len = 0; 2003 rv = trie_search_verbose(trie, &pyld[index].key[0], pyld[index].len, 2004 &pyldptr, &result_key[0], &result_len); 2005 #else 2006 rv = trie_search(trie, &pyld[index].key[0], pyld[index].len, &pyldptr); 2007 #endif 2008 if (rv != SOC_E_NONE) { 2009 LOG_CLI((BSL_META("SEARCH: Key=0x%x 0x%x 0x%x 0x%x 0x%x " 2010 "len %d SEARCH idx:%d failed!!!!\n"), 2011 pyld[index].key[0], pyld[index].key[1], 2012 pyld[index].key[2], pyld[index].key[3], 2013 pyld[index].key[4], pyld[index].len, index)); 2014 break; 2015 } else { 2016 assert(pyldptr == &pyld[index].node); 2017 #ifdef _VERBOSE_SEARCH_ 2018 if (pyld[index].key[0] != result_key[0] || 2019 pyld[index].key[1] != result_key[1] || 2020 pyld[index].key[2] != result_key[2] || 2021 pyld[index].key[3] != result_key[3] || 2022 pyld[index].key[4] != result_key[4] || 2023 pyld[index].len != result_len) { 2024 LOG_CLI((BSL_META(" Found key mismatches with the " 2025 "expected Key !!!! \n"))); 2026 rv = SOC_E_FAIL; 2027 } 2028 #ifdef VERBOSE 2029 LOG_CLI((BSL_META("Lkup[%d] key/len: 0x%x 0x%x 0x%x 0x%x 0x%x/%d " 2030 "Found Key/len: 0x%x 0x%x 0x%x 0x%x 0x%x/%d \n"), 2031 index, pyld[index].key[0], 2032 pyld[index].key[1], pyld[index].key[2], 2033 pyld[index].key[3], pyld[index].key[4], 2034 pyld[index].len, result_key[0], 2035 result_key[1], result_key[2], result_key[3], 2036 result_key[4], result_len)); 2037 #endif 2038 #endif 2039 } 2040 } 2041 } 2042 2043 #ifdef VERBOSE 2044 LOG_CLI((BSL_META("\n============== TRIE DUMP ================\n"))); 2045 trie_dump(trie, NULL, NULL); 2046 LOG_CLI((BSL_META("\n=========================================\n"))); 2047 #endif 2048 2049 /* randomly pickup prefix & delete */ 2050 while(num_deleted < numkey && rv == SOC_E_NONE) { 2051 index = sal_rand() % numkey; 2052 if (pyld[index].len != 0xFFFFFFFF) { 2053 rv = trie_search(trie, &pyld[index].key[0], pyld[index].len, &pyldptr); 2054 if (rv == SOC_E_NONE) { 2055 assert(pyldptr == &pyld[index].node); 2056 rv = trie_delete(trie, &pyld[index].key[0], pyld[index].len, &pyldptr); 2057 2058 #ifdef VERBOSE 2059 LOG_CLI((BSL_META("\n============== TRIE DUMP ================\n"))); 2060 trie_dump(trie, NULL, NULL); 2061 #endif 2062 if (rv == SOC_E_NONE) { 2063 #ifdef LOG 2064 LOG_CLI((BSL_META("Deleted Key=0x%x 0x%x 0x%x 0x%x 0x%x " 2065 "Len=%d idx:%d Num-Key:%d\n"), 2066 pyld[index].key[0], pyld[index].key[1], 2067 pyld[index].key[2], pyld[index].key[3], 2068 pyld[index].key[4], pyld[index].len, 2069 index, num_deleted)); 2070 #endif 2071 pyld[index].len = 0xFFFFFFFF; 2072 num_deleted++; 2073 2074 /* search all keys & figure out breakage right away */ 2075 for (index=0; index < numkey; index++) { 2076 if (pyld[index].len == 0xFFFFFFFF) continue; 2077 2078 rv = trie_search(trie, &pyld[index].key[0], pyld[index].len, &pyldptr); 2079 if (rv != SOC_E_NONE) { 2080 LOG_CLI((BSL_META("ALL SEARCH after delete: " 2081 "Key= 0x%x 0x%x 0x%x 0x%x 0x%x " 2082 "len %d SEARCH idx:%d failed!!!!\n"), 2083 pyld[index].key[0], pyld[index].key[1], 2084 pyld[index].key[2], pyld[index].key[3], 2085 pyld[index].key[4], 2086 pyld[index].len, index)); 2087 break; 2088 } else { 2089 assert(pyldptr == &pyld[index].node); 2090 } 2091 } 2092 } else { 2093 LOG_CLI((BSL_META("Deleted Key=0x%x 0x%x 0x%x 0x%x 0x%x " 2094 "Len=%d idx:%d FAILED!!!\n"), 2095 pyld[index].key[0], pyld[index].key[1], 2096 pyld[index].key[2], pyld[index].key[3], 2097 pyld[index].key[4], 2098 pyld[index].len, index)); 2099 break; 2100 } 2101 } else { 2102 LOG_CLI((BSL_META("SEARCH: Key=0x%x 0x%x 0x%x 0x%x 0x%x " 2103 "len %d SEARCH idx:%d failed!!!!\n"), 2104 pyld[index].key[0], pyld[index].key[1], 2105 pyld[index].key[2], pyld[index].key[3], 2106 pyld[index].key[4], 2107 pyld[index].len, index)); 2108 break; 2109 } 2110 } 2111 } 2112 2113 if (rv == SOC_E_NONE) { 2114 LOG_CLI((BSL_META("\n TEST ID %d passed \n"), id)); 2115 } 2116 else { 2117 LOG_CLI((BSL_META("\n TEST ID %d Failed Num Delete:%d !!!!!!!!\n"), 2118 id, num_deleted)); 2119 } 2120 2121 sal_free(pyld); 2122 trie_destroy(trie); 2123 return rv; 2124 } 2125 2126 /**********************************************/ 2127 /* BPM unit tests */ 2128 /* test cases: 2129 * 1 - insert pivot's with bpm bit masks 2130 * 2 - propagate updated prefix bpm (add/del) 2131 * 3 - fuse node bpm verification 2132 * 4 - split bpm - nop 2133 * 5 - */ 2134 2135 typedef struct _expect_datum_s { 2136 dq_t list; 2137 v6_payload_t *pfx; 2138 trie_t *pfx_trie; 2139 } expect_datum_t; 2140 2141 STATIC int ut_bpm_build_expect_list(trie_node_t *payload, void *user_data) 2142 { 2143 int rv=SOC_E_NONE; 2144 2145 if (payload && payload->type == PAYLOAD) { 2146 trie_node_t *pyldptr; 2147 v6_payload_t *pivot; 2148 expect_datum_t *datum = (expect_datum_t*)user_data; 2149 2150 pivot = TRIE_ELEMENT_GET(v6_payload_t*, payload, node); 2151 /* if the inserted prefix is a best prefix, add the pivot to expected list */ 2152 rv = trie_find_lpm(datum->pfx_trie, &pivot->key[0], pivot->len, &pyldptr); 2153 assert(rv == SOC_E_NONE); 2154 if (pyldptr == &datum->pfx->info.pfx_trie_node) { 2155 /* if pivot is not equal to prefix add to expect list */ 2156 if (!(pivot->key[0] == datum->pfx->key[0] && 2157 pivot->key[1] == datum->pfx->key[1] && 2158 pivot->key[2] == datum->pfx->key[2] && 2159 pivot->key[3] == datum->pfx->key[3] && 2160 pivot->key[4] == datum->pfx->key[4] && 2161 pivot->len == datum->pfx->len)) { 2162 DQ_INSERT_HEAD(&datum->list, &pivot->listnode); 2163 } 2164 } 2165 } 2166 2167 return SOC_E_NONE; 2168 } 2169 2170 STATIC int ut_bpm_propagate_cb(trie_node_t *payload, trie_bpm_cb_info_t *cbinfo) 2171 { 2172 if (payload && cbinfo && payload->type == PAYLOAD) { 2173 v6_payload_t *pivot; 2174 dq_p_t elem; 2175 expect_datum_t *datum = (expect_datum_t*)cbinfo->user_data; 2176 2177 pivot = TRIE_ELEMENT_GET(v6_payload_t*, payload, node); 2178 DQ_TRAVERSE(&datum->list, elem) { 2179 v6_payload_t *velem = DQ_ELEMENT_GET(v6_payload_t*, elem, listnode); 2180 if (velem == pivot) { 2181 DQ_REMOVE(&pivot->listnode); 2182 break; 2183 } 2184 } DQ_TRAVERSE_END(&datum->list, elem); 2185 } 2186 2187 return SOC_E_NONE; 2188 } 2189 2190 STATIC int ut_bpm_propagate_empty_cb(trie_node_t *payload, trie_bpm_cb_info_t *cbinfo) 2191 { 2192 /* do nothing */ 2193 return SOC_E_NONE; 2194 } 2195 2196 STATIC void ut_bpm_dump_expect_list(expect_datum_t *datum, char *str) 2197 { 2198 dq_p_t elem; 2199 if (datum) { 2200 /* dump expected list */ 2201 LOG_CLI((BSL_META("%s \n"), str)); 2202 DQ_TRAVERSE(&datum->list, elem) { 2203 v6_payload_t *velem = DQ_ELEMENT_GET(v6_payload_t*, elem, listnode); 2204 LOG_CLI((BSL_META(" Pivot: 0x%x 0x%x 0x%x 0x%x 0x%x Len: %d \n"), 2205 velem->key[0], velem->key[1], velem->key[2], 2206 velem->key[3], 2207 velem->key[4], velem->len)); 2208 } DQ_TRAVERSE_END(&datum->list, elem); 2209 } 2210 } 2211 2212 #define _MAX_TEST_PIVOTS_ (10) 2213 #define _MAX_BKT_PFX_ (20) 2214 #define _MAX_NUM_PICK (30) 2215 2216 int tmu_taps_bpm_trie_v6_ut(int id, unsigned int seed) 2217 { 2218 int rv = SOC_E_NONE, pivot=0, pfx=0, index=0, dup=0, domain=0; 2219 trie_t *pfx_trie, *trie; 2220 v6_payload_t *pyld = sal_alloc(_MAX_BKT_PFX_ * _MAX_TEST_PIVOTS_ * sizeof(v6_payload_t), "bpm-unit-test"); 2221 v6_payload_t *pivot_pyld = sal_alloc(_MAX_TEST_PIVOTS_ * sizeof(v6_payload_t), "bpm-unit-test"); 2222 trie_node_t *pyldptr = NULL, *newroot; 2223 unsigned int bpm[BITS2WORDS(_MAX_KEY_LEN_)]; 2224 expect_datum_t datum; 2225 trie_bpm_cb_info_t cbinfo; 2226 int num_pick, bpm_pfx_len; 2227 2228 sal_memset(pyld, 0, _MAX_BKT_PFX_ * _MAX_TEST_PIVOTS_ * sizeof(v6_payload_t)); 2229 sal_memset(pivot_pyld, 0, _MAX_TEST_PIVOTS_ * sizeof(v6_payload_t)); 2230 2231 if (seed == 0) { 2232 seed = sal_time(); 2233 sal_srand(seed); 2234 } 2235 2236 trie_init(_MAX_KEY_LEN_, &trie); 2237 trie_init(_MAX_KEY_LEN_, &pfx_trie); 2238 2239 /* populate a random pivot / prefix trie */ 2240 LOG_CLI((BSL_META("Random test: %d Seed: 0x%x \n"), id, seed)); 2241 2242 /* insert a vrf=0,* pivot */ 2243 pivot = 0; 2244 pfx = 0; 2245 pivot_pyld[pivot].key[0] = 0; 2246 pivot_pyld[pivot].key[1] = 0; 2247 pivot_pyld[pivot].key[2] = 0; 2248 pivot_pyld[pivot].key[3] = 0; 2249 pivot_pyld[pivot].key[4] = 0; 2250 pivot_pyld[pivot].len = 0; 2251 trie_init(_MAX_KEY_LEN_, &pivot_pyld[pivot].info.trie); 2252 sal_memset(&bpm[0], 0, BITS2WORDS(_MAX_KEY_LEN_) * sizeof(unsigned int)); 2253 2254 do { 2255 rv = trie_insert(trie, &pivot_pyld[pivot].key[3], &bpm[0], 2256 pivot_pyld[pivot].len, &pivot_pyld[pivot].node); 2257 if (rv != SOC_E_NONE) { 2258 LOG_CLI((BSL_META("FAILED to Insert PIVOT " 2259 "Key=0x%x 0x%x 0x%x 0x%x 0x%x Len=%d idx:%d\n"), 2260 pivot_pyld[pivot].key[0], pivot_pyld[pivot].key[1], 2261 pivot_pyld[pivot].key[2], pivot_pyld[pivot].key[3], 2262 pivot_pyld[pivot].key[4], 2263 pivot_pyld[pivot].len, pivot)); 2264 } else { 2265 if (pivot > 0) { 2266 /* choose a random pivot bucket to fill & split */ 2267 domain = ((unsigned int) sal_rand()) % pivot; 2268 } else { 2269 domain = 0; 2270 } 2271 2272 index = 0; 2273 sal_memset(&bpm[0], 0, BITS2WORDS(_MAX_KEY_LEN_) * sizeof(unsigned int)); 2274 2275 do { 2276 do { 2277 /* add prefix such that lpm of the prefix is the pivot to ensure 2278 * it goes into specific pivot domain */ 2279 pyld[index].len = (unsigned int)sal_rand() % 128; 2280 pyld[index].len += _VRF_LEN_; 2281 2282 pyld[index].key[0] = 0; 2283 pyld[index].key[1] = 0; 2284 pyld[index].key[2] = 0; 2285 pyld[index].key[3] = 0; 2286 if (pyld[index].len > 128) { 2287 pyld[index].key[0] &= MASK(pyld[index].len-128); 2288 pyld[index].key[1] = (unsigned int) sal_rand(); 2289 pyld[index].key[2] = (unsigned int) sal_rand(); 2290 pyld[index].key[3] = (unsigned int) sal_rand(); 2291 pyld[index].key[4] = (unsigned int) sal_rand(); 2292 } else if (pyld[index].len > 96) { 2293 pyld[index].key[1] &= MASK(pyld[index].len-96); 2294 pyld[index].key[2] = (unsigned int) sal_rand(); 2295 pyld[index].key[3] = (unsigned int) sal_rand(); 2296 pyld[index].key[4] = (unsigned int) sal_rand(); 2297 } else if (pyld[index].len > 64) { 2298 pyld[index].key[2] &= MASK(pyld[index].len-64); 2299 pyld[index].key[3] = (unsigned int) sal_rand(); 2300 pyld[index].key[4] = (unsigned int) sal_rand(); 2301 } else if (pyld[index].len > 32) { 2302 pyld[index].key[3] &= MASK(pyld[index].len-32); 2303 pyld[index].key[4] = (unsigned int) sal_rand(); 2304 } else { 2305 pyld[index].key[4] &= MASK(pyld[index].len); 2306 } 2307 2308 dup = ut_check_duplicate(pyld, pfx+index); 2309 if (!dup) { 2310 rv = trie_find_lpm(trie, &pyld[pfx+index].key[0], pyld[pfx+index].len, &pyldptr); 2311 if (SOC_FAILURE(rv)) { 2312 LOG_CLI((BSL_META("\n !! Failed to find LPM pivot " 2313 "for index[%d]:" 2314 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x]" 2315 "!!!!\n"), 2316 pfx, pyld[pfx+index].key[0], 2317 pyld[pfx+index].key[1], 2318 pyld[pfx+index].key[2], 2319 pyld[pfx+index].key[3], 2320 pyld[pfx+index].key[4])); 2321 } 2322 } 2323 } while ((dup || (pyldptr != &pivot_pyld[domain].node)) && SOC_SUCCESS(rv)); 2324 2325 if (SOC_SUCCESS(rv)) { 2326 rv = trie_insert(pivot_pyld[domain].info.trie, 2327 &pyld[pfx+index].key[0], NULL, 2328 pyld[pfx+index].len, &pyld[pfx+index].node); 2329 if (SOC_FAILURE(rv)) { 2330 LOG_CLI((BSL_META("\n !! Failed insert prefix into pivot trie" 2331 " index[%d]:" 2332 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] " 2333 "!!!!\n"), 2334 pfx+index, pyld[pfx+index].key[0], 2335 pyld[pfx+index].key[1], 2336 pyld[pfx+index].key[2], 2337 pyld[pfx+index].key[3], 2338 pyld[pfx+index].key[4])); 2339 } else { 2340 rv = trie_insert(pfx_trie, 2341 &pyld[pfx+index].key[0], NULL, 2342 pyld[pfx+index].len, &pyld[pfx+index].info.pfx_trie_node); 2343 if (SOC_FAILURE(rv)) { 2344 LOG_CLI((BSL_META("\n !! Failed insert prefix into " 2345 "prefix trie index[%d]:" 2346 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x]" 2347 " !!!!\n"), 2348 pfx+index, pyld[pfx+index].key[0], 2349 pyld[pfx+index].key[1], 2350 pyld[pfx+index].key[2], 2351 pyld[pfx+index].key[3], 2352 pyld[pfx+index].key[4])); 2353 } else { 2354 index++; 2355 } 2356 } 2357 } 2358 2359 } while(index < (_MAX_BKT_PFX_/2 - 1) && SOC_SUCCESS(rv)); 2360 2361 /* try to populate prefix where p == v */ 2362 if (pivot > 0) { 2363 /* 25% probability */ 2364 if (((unsigned int) sal_rand() % 4) == 0) { 2365 } 2366 } 2367 2368 #ifdef VERBOSE 2369 LOG_CLI((BSL_META("### Split Domain ID: %d \n"), domain)); 2370 for (i=0; i <= pivot; i++) { 2371 LOG_CLI((BSL_META("\n --- TRIE domain dump: Pivot: " 2372 "0x%x 0x%x 0x%x 0x%x 0x%x len=%d ----- \n"), 2373 pivot_pyld[i].key[0], pivot_pyld[i].key[1], 2374 pivot_pyld[i].key[2], 2375 pivot_pyld[i].key[3], pivot_pyld[i].key[4], 2376 pivot_pyld[i].len)); 2377 trie_dump(pivot_pyld[i].info.trie, ut_print_payload_node, NULL); 2378 } 2379 #endif 2380 2381 if (SOC_SUCCESS(rv) && ++pivot < _MAX_TEST_PIVOTS_) { 2382 pfx += index; 2383 trie_init(_MAX_KEY_LEN_, &pivot_pyld[pivot].info.trie); 2384 /* split the domain & insert a new pivot */ 2385 rv = trie_split(pivot_pyld[domain].info.trie, 2386 _MAX_KEY_LEN_, FALSE, 2387 &pivot_pyld[pivot].key[0], 2388 &pivot_pyld[pivot].len, &newroot, 2389 &bpm[0], FALSE, 1024); 2390 if (SOC_SUCCESS(rv)) { 2391 pivot_pyld[pivot].info.trie->trie = newroot; 2392 LOG_CLI((BSL_META("BPM for split pivot: 0x%x 0x%x 0x%x 0x%x 0x%x " 2393 "/ %d = [0x%x 0x%x 0x%x 0x%x 0x%x] \n"), 2394 pivot_pyld[pivot].key[0], 2395 pivot_pyld[pivot].key[1], 2396 pivot_pyld[pivot].key[2], 2397 pivot_pyld[pivot].key[3], 2398 pivot_pyld[pivot].key[4], 2399 pivot_pyld[pivot].len, 2400 bpm[0], bpm[1], bpm[2], bpm[3], bpm[4])); 2401 } else { 2402 LOG_CLI((BSL_META("\n !!! Failed to split domain trie " 2403 "for domain: %d !!!\n"), domain)); 2404 } 2405 } 2406 } 2407 } while(pivot < _MAX_TEST_PIVOTS_ && SOC_SUCCESS(rv)); 2408 2409 /* pick up the root node on pivot trie & add a prefix shorter than the nearest child. 2410 * This is ripple & create huge propagation */ 2411 /* insert *\/1 into the * bucket so huge propagation kicks in */ 2412 pyld[pfx].key[4] = (unsigned int) sal_rand() % 1; 2413 pyld[pfx].key[3] = 0; 2414 pyld[pfx].key[2] = 0; 2415 pyld[pfx].key[1] = 0; 2416 pyld[pfx].key[0] = 0; 2417 pyld[pfx].len = 1; 2418 do { 2419 dup = ut_check_duplicate(pyld, pfx); 2420 if (!dup) { 2421 rv = trie_find_lpm(trie, &pyld[pfx].key[0], pyld[pfx].len, &pyldptr); 2422 if (SOC_FAILURE(rv)) { 2423 LOG_CLI((BSL_META("\n !! Failed to find LPM pivot for index[%d]:" 2424 "key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] !!!!\n"), 2425 pfx, pyld[pfx].key[0], pyld[pfx].key[1], 2426 pyld[pfx].key[2],pyld[pfx].key[3],pyld[pfx].key[4])); 2427 } 2428 } else { 2429 pyld[pfx].len++; 2430 } 2431 } while(dup && SOC_SUCCESS(rv)); 2432 2433 if (SOC_SUCCESS(rv)) { 2434 rv = trie_insert(pfx_trie, &pyld[pfx].key[0], NULL, 2435 pyld[pfx].len, &pyld[pfx].info.pfx_trie_node); 2436 if (SOC_FAILURE(rv)) { 2437 LOG_CLI((BSL_META("\n !! Failed insert prefix into pivot trie" 2438 " index[%d]:key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] " 2439 "!!!!\n"), 2440 pfx, pyld[pfx].key[0], pyld[pfx].key[1], 2441 pyld[pfx].key[2], pyld[pfx].key[3], pyld[pfx].key[4])); 2442 } else { 2443 DQ_INIT(&datum.list); 2444 datum.pfx = &pyld[pfx]; 2445 datum.pfx_trie = pfx_trie; 2446 /* create expected list of pivot to be propagated */ 2447 trie_traverse(trie, ut_bpm_build_expect_list, &datum, _TRIE_PREORDER_TRAVERSE); 2448 2449 /* dump expected list */ 2450 ut_bpm_dump_expect_list(&datum, "-- Expected Propagation List --"); 2451 } 2452 } 2453 2454 sal_memset(&cbinfo, 0, sizeof(trie_bpm_cb_info_t)); 2455 cbinfo.user_data = &datum; 2456 cbinfo.pfx = &pyld[pfx].key[0]; 2457 cbinfo.len = pyld[pfx].len; 2458 if (pyldptr == NULL) { 2459 assert(0); /* check here for coverity */ 2460 } 2461 rv = trie_v6_pivot_propagate_prefix(pyldptr, 2462 (TRIE_ELEMENT_GET(v6_payload_t*, pyldptr, node))->len, 2463 &pyld[pfx].key[0], pyld[pfx].len, 2464 1, ut_bpm_propagate_cb, &cbinfo); 2465 if (DQ_EMPTY(&datum.list)) { 2466 LOG_CLI((BSL_META("++ Propagation Test Passed \n"))); 2467 } else { 2468 LOG_CLI((BSL_META("!!!!! Propagation Test FAILED !!!!!\n"))); 2469 rv = SOC_E_FAIL; 2470 ut_bpm_dump_expect_list(&datum, "!! Zombies on Propagation List !!"); 2471 assert(0); 2472 } 2473 2474 /* propagate a shorter prefix of an existing pivot 2475 * we should find the bpm 2476 */ 2477 pfx++; 2478 num_pick = 0; 2479 do { 2480 /* randomly pick a pivot */ 2481 index = ((unsigned int) sal_rand()) % pivot; 2482 2483 /* create a prefix shorter */ 2484 pyld[pfx].len = ((unsigned int) sal_rand()) % pivot_pyld[index].len; 2485 sal_memcpy(pyld[pfx].key, pivot_pyld[index].key, _MAX_KEY_WORDS_*sizeof(uint32)); 2486 rv = taps_key_shift(_MAX_KEY_LEN_, pyld[pfx].key, pivot_pyld[index].len, 2487 (pivot_pyld[index].len-pyld[pfx].len)); 2488 2489 if (pyld[pfx].len >= 1) { 2490 /* propagate add len=0 */ 2491 rv = trie_v6_pivot_propagate_prefix(trie->trie, 2492 (TRIE_ELEMENT_GET(v6_payload_t*, trie->trie, node))->len, 2493 &pyld[pfx].key[0], 0, 2494 1, ut_bpm_propagate_empty_cb, 2495 &cbinfo); 2496 2497 if (SOC_FAILURE(rv)) { 2498 LOG_CLI((BSL_META("!!!!! BPM search Test FAILED to propagate " 2499 "add len=0!!!!!\n"))); 2500 assert(0); 2501 } 2502 2503 /* propagate add */ 2504 rv = trie_v6_pivot_propagate_prefix(trie->trie, 2505 (TRIE_ELEMENT_GET(v6_payload_t*, trie->trie, node))->len, 2506 &pyld[pfx].key[0], pyld[pfx].len, 2507 1, ut_bpm_propagate_empty_cb, 2508 &cbinfo); 2509 if (SOC_FAILURE(rv)) { 2510 LOG_CLI((BSL_META("!!!!! BPM search Test FAILED to propagate add \n" 2511 " index[%d]:key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] " 2512 "len=%d!!!!\n"), 2513 pfx, pyld[pfx].key[0], pyld[pfx].key[1], 2514 pyld[pfx].key[2], pyld[pfx].key[3], 2515 pyld[pfx].key[4], pyld[pfx].len)); 2516 assert(0); 2517 } 2518 2519 /* perform bpm lookup on the pivot, we should find the pyld[pfx].len */ 2520 rv = trie_find_prefix_bpm(trie, (unsigned int *)&(pivot_pyld[index].key[0]), 2521 pivot_pyld[index].len, (unsigned int *)&bpm_pfx_len); 2522 if (SOC_FAILURE(rv) || (bpm_pfx_len != pyld[pfx].len)) { 2523 LOG_CLI((BSL_META("!!!!! BPM search Test FAILDED after propagate " 2524 "add !!!!!\n"))); 2525 assert(0); 2526 } 2527 2528 /* propagate delete */ 2529 rv = trie_v6_pivot_propagate_prefix(trie->trie, 2530 (TRIE_ELEMENT_GET(v6_payload_t*, trie->trie, node))->len, 2531 &pyld[pfx].key[0], pyld[pfx].len, 2532 0, ut_bpm_propagate_empty_cb, 2533 &cbinfo); 2534 2535 if (SOC_FAILURE(rv)) { 2536 LOG_CLI((BSL_META("!!!!! BPM search Test FAILED to propagate add \n" 2537 " index[%d]:key[0x%08x:0x%08x:0x%08x:0x%08x:0x%08x] " 2538 "len=%d!!!!\n"), 2539 pfx, pyld[pfx].key[0], pyld[pfx].key[1], 2540 pyld[pfx].key[2], pyld[pfx].key[3], 2541 pyld[pfx].key[4], pyld[pfx].len)); 2542 assert(0); 2543 } 2544 2545 /* perform bpm lookup on the pivot, we should find the len==0 */ 2546 rv = trie_find_prefix_bpm(trie, (unsigned int *)&(pivot_pyld[index].key[0]), 2547 pivot_pyld[index].len, (unsigned int *)&bpm_pfx_len); 2548 if (SOC_FAILURE(rv) || (bpm_pfx_len != 0)) { 2549 LOG_CLI((BSL_META("!!!!! BPM search Test FAILDED after propagate " 2550 "delete !!!!!\n"))); 2551 assert(0); 2552 } 2553 2554 num_pick = _MAX_NUM_PICK+1; 2555 } 2556 num_pick++; 2557 } while(num_pick<_MAX_NUM_PICK); 2558 2559 if (num_pick <= _MAX_NUM_PICK) { 2560 LOG_CLI((BSL_META("!!!!! BPM search Test 2 Skipped after " 2561 "tried %d times!!!!!\n"), _MAX_NUM_PICK)); 2562 } else { 2563 LOG_CLI((BSL_META("!!!!! BPM search Test 2 Passed!!!!!\n"))); 2564 } 2565 2566 LOG_CLI((BSL_META("\n ----- Prefix Trie dump ----- \n"))); 2567 trie_dump(pfx_trie, ut_print_prefix_payload_node, NULL); 2568 2569 LOG_CLI((BSL_META("\n ++++++++ Trie dump ++++++++ \n"))); 2570 trie_dump(trie, ut_print_payload_node, NULL); 2571 2572 /* clean up */ 2573 for (index=0; index < pivot; index++) { 2574 LOG_CLI((BSL_META("\n ddddddd dump dddddddd \n"))); 2575 trie_dump(pivot_pyld[index].info.trie, ut_print_payload_node, NULL); 2576 trie_destroy(pivot_pyld[index].info.trie); 2577 } 2578 2579 sal_free(pyld); 2580 sal_free(pivot_pyld); 2581 trie_destroy(trie); 2582 trie_destroy(pfx_trie); 2583 return rv; 2584 } 2585 2586 /**********************************************/ 2587 2588 #endif /* BCM_TRIDENT2_SUPPORT */ 2589 #endif /* ALPM_ENABLE */