alpm_lib_trie6.c (46827B)
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 #include <shared/util.h> 16 #include <sal/appl/sal.h> 17 #include <sal/core/libc.h> 18 #include <sal/core/time.h> 19 20 #include <bcm_int/esw/alpm_lib_trie.h> 21 22 #include <soc/esw/sbDq.h> 23 24 extern void * alpm_util_alloc(unsigned int sz, char *s); 25 extern void alpm_util_free(void *addr); 26 27 /* 28 * 29 * Function: 30 * taps_key_shift 31 * Input: 32 * max_key_size -- max number of bits in the key 33 * ipv4 == 48 34 * ipv4 == 144 35 * key -- uint32 array head. Only "length" number of bits 36 * is passed in. 37 * for ipv4. Key[0].bit15-0 is key bits 47-32 38 * Key[1] is key bits 31-0 39 * for ipv6. Key[0].bit15-0 is key bits 143-128 40 * Key[1-4] is key bits 127-0 41 * length-- number of valid bits in key array. This would be 42 * valid MSB bits of the route. For example, 43 * (vrf=0x1234, ip=0xf0000000, length=20) would store 44 * as key[0] = 0, key[1]=0x1234F, length=20. 45 * shift -- positive means right shift, negative means left shift 46 * routine will check if the shifted key is out of 47 * max_key_size boundary. 48 */ 49 static int taps_key_shift(uint32 *key, uint32 length, int32 shift) 50 { 51 int word_idx, lsb; 52 53 if (shift > 0) { 54 /* right shift */ 55 for (lsb = shift, word_idx=BITS2WORDS(_MAX_KEY_LEN_144_)-1; 56 word_idx >=0; 57 lsb+=32, word_idx--) { 58 if (lsb < length) { 59 key[word_idx] = _TAPS_GET_KEY_BITS(key, lsb, ((length-lsb)>=32)?32:(length-lsb)); 60 } else { 61 key[word_idx] = 0; 62 } 63 } 64 } else if (shift < 0) { 65 /* left shift */ 66 shift = 0 - shift; 67 68 /* whole words shifting first */ 69 for (word_idx = 0; 70 ((shift/32)!=0) && (word_idx < BITS2WORDS(_MAX_KEY_LEN_144_)); 71 word_idx++) { 72 if ((word_idx + (shift/32)) >= BITS2WORDS(_MAX_KEY_LEN_144_)) { 73 key[word_idx]=0; 74 } else { 75 key[word_idx] = key[word_idx + (shift/32)]; 76 } 77 } 78 79 /* shifting remaining bits */ 80 for (word_idx = 0; 81 ((shift%32)!=0) && (word_idx < BITS2WORDS(_MAX_KEY_LEN_144_)); 82 word_idx++) { 83 if (word_idx == TP_BITS2IDX(0)) { 84 /* at bit 0 word, next word doesn't exist */ 85 key[word_idx] = _SHL(key[word_idx], (shift%_NUM_WORD_BITS_)); 86 } else { 87 key[word_idx] = _SHL(key[word_idx], (shift%_NUM_WORD_BITS_)) | \ 88 TRIE_SHR(key[word_idx+1], _NUM_WORD_BITS_-(shift%_NUM_WORD_BITS_), _NUM_WORD_BITS_); 89 } 90 } 91 92 /* mask off bits higher than max_key_size */ 93 key[0] &= BITMASK(_MAX_KEY_LEN_144_%32); 94 } 95 96 return SOC_E_NONE; 97 } 98 99 100 /********************************************************/ 101 /* Get a chunk of bits from a key (MSB bit - on word0, lsb on word 1).. 102 */ 103 static uint32 _alpm_lib_key_get_bits(uint32 *key, 104 uint32 pos /* 1based, msb bit position */, 105 uint32 len) 106 { 107 /* use Macro, convert to what's required by Macro */ 108 return _TAPS_GET_KEY_BITS(key, pos-len, len); 109 } 110 111 /* 112 * Assumes the layout for 113 * 0 - most significant word 114 * MAX_KEY_WORDS - least significant word 115 * eg., for key size of 48, word0-[bits 48-32] word1-[bits31-0] 116 */ 117 static int _key_append(uint32 *key, 118 uint32 *length, 119 uint32 skip_addr, 120 uint32 skip_len) 121 { 122 int rv=SOC_E_NONE; 123 124 rv = taps_key_shift(key, *length, 0-(int)skip_len); 125 if (SOC_SUCCESS(rv)) { 126 key[KEY144_BIT2IDX(1)] |= skip_addr; 127 *length += skip_len; 128 } 129 130 return rv; 131 } 132 133 /* 134 * Function: 135 * lcplen 136 * Purpose: 137 * returns longest common prefix length provided a key & skip address 138 */ 139 static uint32 140 lcplen(uint32 *key, uint32 len1, uint32 skip_addr, uint32 len2) 141 { 142 uint32 diff; 143 uint32 lcp = len1 < len2 ? len1 : len2; 144 145 if ((len1 == 0) || (len2 == 0)) { 146 return 0; 147 } 148 149 diff = _alpm_lib_key_get_bits(key, len1, lcp); 150 diff ^= (TRIE_SHR(skip_addr, len2 - lcp, _MAX_SKIP_LEN_) & TRIE_MASK(lcp)); 151 152 while (diff) { 153 diff >>= 1; 154 --lcp; 155 } 156 157 return lcp; 158 } 159 160 int _alpm_lib_trie_v6_search(alpm_lib_trie_node_t *trie, 161 uint32 *key, 162 uint32 length, 163 alpm_lib_trie_node_t **payload, 164 uint32 *result_key, 165 uint32 *result_len, 166 uint32 dump, 167 uint32 find_pivot) 168 { 169 uint32 lcp=0; 170 int bit=0, rv=SOC_E_NONE; 171 172 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 173 174 if (dump) { 175 _alpm_lib_print_trie_node(trie, (uint32 *)1); 176 } 177 178 if (length > trie->skip_len) { 179 if (lcp == trie->skip_len) { 180 bit = (key[KEY144_BIT2IDX(length - lcp)] & \ 181 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 182 if (dump) { 183 LOG_CLI((BSL_META(" Length: %d Next-Bit[%d] \n"), length, bit)); 184 } 185 186 if (result_key) { 187 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 188 if (SOC_FAILURE(rv)) return rv; 189 } 190 191 /* based on next bit branch left or right */ 192 if (trie->child[bit]) { 193 if (result_key) { 194 rv = _key_append(result_key, result_len, bit, 1); 195 if (SOC_FAILURE(rv)) return rv; 196 } 197 198 return _alpm_lib_trie_v6_search(trie->child[bit], key, 199 length - lcp - 1, payload, 200 result_key, result_len, dump, find_pivot); 201 } else { 202 return SOC_E_NOT_FOUND; /* not found */ 203 } 204 } else { 205 return SOC_E_NOT_FOUND; /* not found */ 206 } 207 } else if (length == trie->skip_len) { 208 if (lcp == length) { 209 if (dump) { 210 LOG_CLI((BSL_META(": MATCH \n"))); 211 } 212 *payload = trie; 213 if (trie->type != trieNodeTypePayload && !find_pivot) { 214 /* no assert here, possible during dbucket search 215 * due to 1* and 0* bucket search 216 */ 217 return SOC_E_NOT_FOUND; 218 } 219 if (result_key) { 220 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 221 if (SOC_FAILURE(rv)) return rv; 222 } 223 return SOC_E_NONE; 224 } 225 else return SOC_E_NOT_FOUND; 226 } else { 227 if (lcp == length && find_pivot) { 228 *payload = trie; 229 if (result_key) { 230 rv = _key_append(result_key, result_len, trie->skip_addr, trie->skip_len); 231 if (SOC_FAILURE(rv)) return rv; 232 } 233 } 234 return SOC_E_NOT_FOUND; /* not found */ 235 } 236 } 237 238 /* 239 * Internal function for LPM match searching. 240 * callback on all payload nodes if cb != NULL. 241 */ 242 int _alpm_lib_trie_v6_find_lpm(alpm_lib_trie_node_t *trie, 243 uint32 *key, 244 uint32 length, 245 alpm_lib_trie_node_t **payload, 246 alpm_lib_trie_callback_f cb, 247 void *user_data, 248 uint32 exclude_self) 249 { 250 uint32 lcp=0; 251 int bit=0, rv=SOC_E_NONE; 252 253 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 254 255 if ((length > trie->skip_len) && (lcp == trie->skip_len)) { 256 if (trie->type == trieNodeTypePayload) { 257 /* lpm cases */ 258 if (payload != NULL) { 259 /* update lpm result */ 260 *payload = trie; 261 } 262 263 if (cb != NULL) { 264 /* callback with any nodes which is shorter and matches the prefix */ 265 rv = cb(trie, user_data); 266 if (SOC_FAILURE(rv)) { 267 /* early bailout if there is error in callback handling */ 268 return rv; 269 } 270 } 271 } 272 273 bit = (key[KEY144_BIT2IDX(length - lcp)] & \ 274 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 275 276 /* based on next bit branch left or right */ 277 if (trie->child[bit]) { 278 return _alpm_lib_trie_v6_find_lpm(trie->child[bit], key, length - lcp - 1, 279 payload, cb, user_data, exclude_self); 280 } 281 } else if ((length == trie->skip_len) && (lcp == length)) { 282 if (trie->type == trieNodeTypePayload) { 283 /* exact match case */ 284 if (payload != NULL && !exclude_self) { 285 /* lpm is exact match */ 286 *payload = trie; 287 } 288 289 if (cb != NULL) { 290 /* callback with the exact match node */ 291 rv = cb(trie, user_data); 292 if (SOC_FAILURE(rv)) { 293 /* early bailout if there is error in callback handling */ 294 return rv; 295 } 296 } 297 } 298 } 299 return rv; 300 } 301 302 /* 303 * Function: 304 * _alpm_lib_trie_v6_skip_node_free 305 * Purpose: 306 * Destroy a chain of alpm_lib_trie_node_t that has the target node at the end. 307 * The target node is not necessarily trieNodeTypePayload type, but all nodes 308 * on the chain except for the end must have only one branch. 309 * Input: 310 * key -- target key 311 * length -- target key length 312 * free_end -- free 313 */ 314 int _alpm_lib_trie_v6_skip_node_free(alpm_lib_trie_node_t *trie, 315 uint32 *key, 316 uint32 length) 317 { 318 uint32 lcp=0; 319 int bit=0, rv=SOC_E_NONE; 320 321 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 322 323 if (length > trie->skip_len) { 324 325 if (lcp == trie->skip_len) { 326 bit = (key[KEY144_BIT2IDX(length - lcp)] & \ 327 (1 << ((length - lcp - 1) % _NUM_WORD_BITS_))) ? 1:0; 328 329 /* There should be only one branch on the chain until the end node */ 330 if (!trie->child[0] == !trie->child[1]) { 331 return SOC_E_PARAM; 332 } 333 334 /* based on next bit branch left or right */ 335 if (trie->child[bit]) { 336 rv = _alpm_lib_trie_v6_skip_node_free(trie->child[bit], key, 337 length - lcp - 1); 338 if (SOC_SUCCESS(rv)) { 339 assert(trie->type == trieNodeTypeInternal); 340 alpm_util_free(trie); 341 } 342 return rv; 343 } else { 344 return SOC_E_NOT_FOUND; /* not found */ 345 } 346 } else { 347 return SOC_E_NOT_FOUND; /* not found */ 348 } 349 } else if (length == trie->skip_len) { 350 if (lcp == length) { 351 /* the end node is not necessarily type payload. */ 352 353 return SOC_E_NONE; 354 } 355 else return SOC_E_NOT_FOUND; 356 } else { 357 return SOC_E_NOT_FOUND; /* not found */ 358 } 359 } 360 361 362 /* 363 * Function: 364 * _alpm_lib_trie_v6_skip_node_alloc 365 * Purpose: 366 * create a chain of alpm_lib_trie_node_t that has the payload at the end. 367 * each node in the chain can skip upto _MAX_SKIP_LEN number of bits, 368 * while the child pointer in the chain represent 1 bit. So totally 369 * each node can absorb (_MAX_SKIP_LEN+1) bits. 370 * Input: 371 * key -- 372 * msb -- 373 * skip_len -- skip_len of the whole chain 374 * payload -- payload node we want to insert 375 * count -- child count 376 * Output: 377 * node -- return pointer of the starting node of the chain. 378 */ 379 int _alpm_lib_trie_v6_skip_node_alloc(alpm_lib_trie_node_t **node, 380 uint32 *key, 381 uint32 msb, /* NOTE: valid msb position 1 based, 0 means skip0/0 node */ 382 uint32 skip_len, 383 alpm_lib_trie_node_t *payload, 384 uint32 count) /* payload count underneath - mostly 1 except some tricky cases */ 385 { 386 int lsb=0, msbpos=0, lsbpos=0, bit=0, index; 387 alpm_lib_trie_node_t *child = NULL, *skip_node = NULL; 388 389 /* calculate lsb bit position, also 1 based */ 390 lsb = ((msb)? msb + 1 - skip_len : msb); 391 392 if (msb) { 393 for (index = BITS2SKIPOFF(lsb), lsbpos = lsb - 1; index <= BITS2SKIPOFF(msb); index++) { 394 /* each loop process _MAX_SKIP_LEN number of bits?? */ 395 if (lsbpos == lsb-1) { 396 /* (lsbpos == lsb-1) is only true for first node (loop) here */ 397 skip_node = payload; 398 } else { 399 /* other nodes need to be created */ 400 skip_node = alpm_util_alloc(sizeof(alpm_lib_trie_node_t), "trie_node"); 401 } 402 403 /* init memory */ 404 sal_memset(skip_node, 0, sizeof(alpm_lib_trie_node_t)); 405 406 /* calculate msb bit position of current chunk of bits we are processing */ 407 msbpos = index * _MAX_SKIP_LEN_ - 1; 408 if (msbpos > msb-1) msbpos = msb-1; 409 410 /* calculate the skip_len of the created node */ 411 if (msbpos - lsbpos < _MAX_SKIP_LEN_) { 412 skip_node->skip_len = msbpos - lsbpos + 1; 413 } else { 414 skip_node->skip_len = _MAX_SKIP_LEN_; 415 } 416 417 /* calculate the skip_addr (skip_length number of bits). 418 * skip might be skipping bits on 2 different words 419 * if msb & lsb spawns 2 word boundary in worst case 420 */ 421 if (BITS2WORDS(msbpos+1) != BITS2WORDS(lsbpos+1)) { 422 /* pull snippets from the different words & fuse */ 423 skip_node->skip_addr = key[KEY144_BIT2IDX(msbpos+1)] & TRIE_MASK((msbpos+1) % _NUM_WORD_BITS_); 424 skip_node->skip_addr = _SHL(skip_node->skip_addr, skip_node->skip_len - ((msbpos+1) % _NUM_WORD_BITS_)); 425 skip_node->skip_addr |= _SHR(key[KEY144_BIT2IDX(lsbpos+1)],(lsbpos % _NUM_WORD_BITS_)); 426 } else { 427 skip_node->skip_addr = _SHR(key[KEY144_BIT2IDX(msbpos+1)], (lsbpos % _NUM_WORD_BITS_)); 428 } 429 430 /* set up the chain of child pointer, first node has no child since "child" was inited to NULL */ 431 if (child) { 432 skip_node->child[bit] = child; 433 } 434 435 /* calculate child pointer for next loop. NOTE: skip_addr has not been masked 436 * so we still have the child bit in the skip_addr here. 437 */ 438 bit = (skip_node->skip_addr & _SHL(1, skip_node->skip_len - 1)) ? 1:0; 439 440 /* calculate node type */ 441 if (lsbpos == lsb-1) { 442 /* first node is payload */ 443 skip_node->type = trieNodeTypePayload; 444 } else { 445 /* other nodes are internal nodes */ 446 skip_node->type = trieNodeTypeInternal; 447 } 448 449 /* all internal nodes will have the same "count" as the payload node */ 450 skip_node->count = count; 451 452 /* advance lsb to next word */ 453 lsbpos += skip_node->skip_len; 454 455 /* for all child nodes 0/1 is implicitly obsorbed on parent */ 456 if (msbpos != msb-1) { 457 /* msbpos == (msb-1) is only true for the first node */ 458 skip_node->skip_len--; 459 } 460 skip_node->skip_addr &= TRIE_MASK(skip_node->skip_len); 461 child = skip_node; 462 } 463 } else { 464 /* skip_len == 0 case, create a payload node with skip_len = 0 465 * bit 0 and bit "skip_len" are same bit (bit 0). 466 */ 467 skip_node = payload; 468 sal_memset(skip_node, 0, sizeof(alpm_lib_trie_node_t)); 469 skip_node->type = trieNodeTypePayload; 470 skip_node->count = count; 471 } 472 473 *node = skip_node; 474 return SOC_E_NONE; 475 } 476 477 int _alpm_lib_trie_v6_insert(alpm_lib_trie_node_t *trie, uint32 *key, uint32 length, 478 alpm_lib_trie_node_t *payload, /* payload node */ 479 alpm_lib_trie_node_t **child, /* child pointer if the child is modified */ 480 int child_count) 481 { 482 uint32 lcp; 483 int rv=SOC_E_NONE, bit=0; 484 alpm_lib_trie_node_t *node = NULL; 485 486 *child = NULL; 487 488 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 489 490 /* insert cases: 491 * 1 - new key could be the parent of existing node 492 * 2 - new node could become the child of a existing node 493 * 3 - internal node could be inserted and the key becomes one of child 494 * 4 - internal node is converted to a payload node */ 495 496 /* if the new key qualifies as new root do the inserts here */ 497 if (lcp == length) { /* guaranteed: length < _MAX_SKIP_LEN_ */ 498 if (trie->skip_len == lcp) { 499 if (trie->type != trieNodeTypeInternal) { 500 /* duplicate */ 501 return SOC_E_EXISTS; 502 } else { 503 /* change the internal node to payload node */ 504 _TRIE_NODE_CLONE_(payload,trie); 505 alpm_util_free(trie); 506 payload->type = trieNodeTypePayload; 507 payload->count += child_count; 508 *child = payload; 509 return SOC_E_NONE; 510 } 511 } else { /* skip length can never be less than lcp implcitly here */ 512 /* this node is new parent for the old trie node */ 513 /* lcp is the new skip length */ 514 _TRIE_NODE_CLONE_(payload,trie); 515 *child = payload; 516 517 bit = (trie->skip_addr & _SHL(1,trie->skip_len - length - 1)) ? 1 : 0; 518 trie->skip_addr &= TRIE_MASK(trie->skip_len - length - 1); 519 trie->skip_len -= (length + 1); 520 521 payload->skip_addr = (length > 0) ? key[KEY144_BIT2IDX(length)] : 0; 522 payload->skip_addr &= TRIE_MASK(length); 523 payload->skip_len = length; 524 payload->child[bit] = trie; 525 payload->child[!bit] = NULL; 526 payload->type = trieNodeTypePayload; 527 payload->count += child_count; 528 } 529 } else if (lcp == trie->skip_len) { 530 /* key length is implictly greater than lcp here */ 531 /* decide based on key's next applicable bit */ 532 bit = (key[KEY144_BIT2IDX(length-lcp)] & 533 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 534 535 if (!trie->child[bit]) { 536 /* the key is going to be one of the child of existing node */ 537 /* should be the child */ 538 rv = _alpm_lib_trie_v6_skip_node_alloc(&node, key, 539 length-lcp-1, /* 0 based msbit position */ 540 length-lcp-1, 541 payload, child_count); 542 if (SOC_SUCCESS(rv)) { 543 trie->child[bit] = node; 544 trie->count += child_count; 545 } else { 546 LOG_CLI((BSL_META("\n Error on trie skip node allocaiton [%d]!!!!\n"), 547 rv)); 548 } 549 } else { 550 rv = _alpm_lib_trie_v6_insert(trie->child[bit], 551 key, length - lcp - 1, 552 payload, child, child_count); 553 if (SOC_SUCCESS(rv)) { 554 trie->count += child_count; 555 if (*child != NULL) { /* chande the old child pointer to new child */ 556 trie->child[bit] = *child; 557 *child = NULL; 558 } 559 } 560 } 561 } else { 562 alpm_lib_trie_node_t *newchild = NULL; 563 564 /* need to introduce internal nodes */ 565 node = alpm_util_alloc(sizeof(alpm_lib_trie_node_t), "trie-node"); 566 _TRIE_NODE_CLONE_(node, trie); 567 568 rv = _alpm_lib_trie_v6_skip_node_alloc(&newchild, key, 569 ((lcp)?length-lcp-1:length-1), 570 length - lcp - 1, 571 payload, child_count); 572 if (SOC_SUCCESS(rv)) { 573 bit = (key[KEY144_BIT2IDX(length-lcp)] & 574 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1: 0; 575 576 node->child[!bit] = trie; 577 node->child[bit] = newchild; 578 node->type = trieNodeTypeInternal; 579 node->skip_addr = _SHR(trie->skip_addr,trie->skip_len - lcp); 580 node->skip_len = lcp; 581 node->count += child_count; 582 *child = node; 583 584 trie->skip_addr &= TRIE_MASK(trie->skip_len - lcp - 1); 585 trie->skip_len -= (lcp + 1); 586 } else { 587 LOG_CLI((BSL_META("\n Error on trie skip node allocaiton [%d]!!!!\n"), rv)); 588 alpm_util_free(node); 589 } 590 } 591 592 return rv; 593 } 594 595 int 596 _alpm_lib_trie_v6_delete(alpm_lib_trie_node_t *trie, uint32 *key, uint32 length, alpm_lib_trie_node_t **payload, alpm_lib_trie_node_t **child) 597 { 598 uint32 lcp; 599 int rv=SOC_E_NONE, bit=0; 600 alpm_lib_trie_node_t *node = NULL; 601 602 *child = NULL; 603 604 /* check a section of key, return the number of matched bits and value of next bit */ 605 lcp = lcplen(key, length, trie->skip_addr, trie->skip_len); 606 607 if (length > trie->skip_len) { 608 609 if (lcp == trie->skip_len) { 610 611 bit = (key[KEY144_BIT2IDX(length-lcp)] & 612 (1 << ((length - lcp -1) % _NUM_WORD_BITS_))) ? 1:0; 613 614 /* based on next bit branch left or right */ 615 if (trie->child[bit]) { 616 /* has child node, keep searching */ 617 rv = _alpm_lib_trie_v6_delete(trie->child[bit], key, length - lcp - 1, payload, child); 618 619 if (rv == SOC_E_BUSY) { 620 trie->child[bit] = NULL; /* alpm_util_free the child */ 621 rv = SOC_E_NONE; 622 trie->count--; 623 624 if (trie->type == trieNodeTypeInternal) { 625 626 bit = (bit==0)?1:0; 627 628 if (trie->child[bit] == NULL) { 629 /* parent and child connected, alpm_util_free the middle-node itself */ 630 alpm_util_free(trie); 631 rv = SOC_E_BUSY; 632 } else { 633 /* fuse the parent & child */ 634 if (trie->skip_len + trie->child[bit]->skip_len + 1 <= 635 _MAX_SKIP_LEN_) { 636 *child = trie->child[bit]; 637 rv = _alpm_lib_trie_fuse_child(trie, bit); 638 if (rv != SOC_E_NONE) { 639 *child = NULL; 640 } 641 } 642 } 643 } 644 } else if (SOC_SUCCESS(rv)) { 645 trie->count--; 646 /* update child pointer if applicable */ 647 if (*child != NULL) { 648 trie->child[bit] = *child; 649 *child = NULL; 650 } 651 } 652 } else { 653 /* no child node case 0: not found */ 654 rv = SOC_E_NOT_FOUND; 655 } 656 } else { 657 /* some bits are not matching, case 0: not found */ 658 rv = SOC_E_NOT_FOUND; 659 } 660 } else if (length == trie->skip_len) { 661 /* when length equal to skip_len, unless this is a payload node 662 * and it's an exact match (lcp == length), we can not found a match 663 */ 664 if (!((lcp == length) && (trie->type == trieNodeTypePayload))) { 665 rv = SOC_E_NOT_FOUND; 666 } else { 667 /* payload node can be deleted */ 668 /* if this node has 2 children update it to internal node */ 669 rv = SOC_E_NONE; 670 671 if (trie->child[0] && trie->child[1] ) { 672 /* the node has 2 children, update it to internal node */ 673 node = alpm_util_alloc(sizeof(alpm_lib_trie_node_t), "trie_node"); 674 _TRIE_NODE_CLONE_(node, trie); 675 node->type = trieNodeTypeInternal; 676 node->count--; 677 *child = node; 678 } else if (trie->child[0] || trie->child[1] ) { 679 /* if this node has 1 children fuse the children with this node */ 680 bit = (trie->child[0]) ? 0:1; 681 trie->count--; 682 if (trie->skip_len + trie->child[bit]->skip_len + 1 <= _MAX_SKIP_LEN_) { 683 684 /* able to fuse the node with its child node */ 685 *child = trie->child[bit]; 686 rv = _alpm_lib_trie_fuse_child(trie, bit); 687 if (rv != SOC_E_NONE) { 688 *child = NULL; 689 } 690 } else { 691 /* convert it to internal node, we need to alloc new memory for internal nodes 692 * since the old payload node memory will be freed by caller 693 */ 694 node = alpm_util_alloc(sizeof(alpm_lib_trie_node_t), "trie_node"); 695 _TRIE_NODE_CLONE_(node, trie); 696 node->type = trieNodeTypeInternal; 697 *child = node; 698 } 699 } else { 700 rv = SOC_E_BUSY; 701 } 702 703 *payload = trie; 704 } 705 } else { 706 /* key length is shorter, no match if it's internal node, 707 * will not exact match even if this is a payload node 708 */ 709 rv = SOC_E_NOT_FOUND; /* case 0: not found */ 710 } 711 712 return rv; 713 } 714 715 STATIC INLINE int 716 _alpm_lib_trie_v6_splitable(alpm_lib_trie_node_t *trie, alpm_lib_trie_node_t *child, 717 alpm_lib_trie_callback_ext_f cb, void *user_data, 718 int max_count, int max_split_count) 719 { 720 /* 721 * NOTE: 722 * ABS(trie->count * 2 - max_count) actually means 723 * ABS(trie->count - (max_count - trie->count)) 724 * which means the count's distance to half depth of the bucket 725 */ 726 int do_split = 0; 727 int half_count = (max_count + 1) >> 1; 728 729 if (cb && cb(trie, child, NULL, user_data)) { 730 do_split = 1; 731 } else if (trie->count <= max_split_count && trie->count != max_count) { 732 if (child == NULL) { 733 do_split = 1; 734 } else if (trie->count >= half_count && child->count <= half_count) { 735 do_split = 1; 736 } else if (ABS(child->count * 2 - max_count) > 737 ABS(trie->count * 2 - max_count)) { 738 do_split = 1; 739 } 740 } 741 742 return do_split; 743 } 744 745 /* 746 * Function: 747 * trie_v6_split 748 * Purpose: 749 * Split the trie into 2 based on optimum pivot 750 * NOTE: 751 * max_split_len -- split will make sure the split point 752 * has a length shorter or equal to the max_split_len 753 * unless this will cause a no-split (all prefixs 754 * stays below the split point) 755 * split_to_pair -- used only when the split point will be 756 * used to create a pair of tries later (i.e: dbucket 757 * pair. we assume the split point itself will always be 758 * put into 0* trie if itself is a payload/prefix) 759 */ 760 int _alpm_lib_trie_v6_split(alpm_lib_trie_node_t *trie, 761 uint32 *pivot, 762 uint32 *length, 763 uint32 *split_count, 764 alpm_lib_trie_node_t **split_node, 765 alpm_lib_trie_node_t **child, 766 const uint32 max_count, 767 const uint32 max_split_len, 768 alpm_lib_trie_split_state_t *state, 769 alpm_lib_trie_callback_ext_f cb, 770 void *user_data, 771 int max_split_count) 772 { 773 int bit=0, rv=SOC_E_NONE; 774 775 if (trie->child[0] && trie->child[1]) { 776 bit = (trie->child[0]->count > 777 trie->child[1]->count) ? 0:1; 778 } else { 779 bit = (trie->child[0])?0:1; 780 } 781 782 /* start building the pivot */ 783 rv = _key_append(pivot, length, trie->skip_addr, trie->skip_len); 784 if (SOC_FAILURE(rv)) return rv; 785 786 /* 787 * split logic to make sure the split length is shorter than the 788 * requested max_split_len, unless we don't actully split the 789 * tree if we stop here. 790 * if (*length > max_split_len) && (trie->count != max_count) { 791 * need to split at or above this node. might need to split the node in middle 792 * } else if ((ABS(child count*2 - max_count) > ABS(count*2 - max_count)) || 793 * ((*length == max_split_len) && (trie->count != max_count))) { 794 * (the check above imply trie->count != max_count, so also imply *length < max_split_len) 795 * need to split at this node. 796 * } else { 797 * keep searching, will be better split at longer pivot. 798 * } 799 */ 800 if ((*length > max_split_len) && (trie->count != max_count)) { 801 /* the pivot is getting too long, we better split at this node for 802 * better bucket capacity efficiency if we can. We can split if 803 * the trie node has a count != max_count, which means the 804 * resulted new trie will not have all pivots (FULL) 805 */ 806 if ((trieSplitStatePayloadSplit == *state) && 807 (trie->type == trieNodeTypeInternal)) { 808 *state = trieSplitStatePayloadSplitDone; 809 } else { 810 if (((*length - max_split_len) > trie->skip_len) && (trie->skip_len == 0)) { 811 /* the length is longer than max_split_len, and the trie->skip_len is 0, 812 * so the best we can do is use the node as the split point 813 */ 814 *split_node = trie; 815 *split_count = trie->count; 816 817 *state = trieSplitStatePruneNodes; 818 return rv; 819 } 820 821 /* we need to insert a node and use it as split point */ 822 *split_node = alpm_util_alloc(sizeof(alpm_lib_trie_node_t), "trie_node"); 823 sal_memset((*split_node), 0, sizeof(alpm_lib_trie_node_t)); 824 (*split_node)->type = trieNodeTypeInternal; 825 (*split_node)->count = trie->count; 826 827 if ((*length - max_split_len) > trie->skip_len) { 828 /* the length is longer than the max_split_len, and the trie->skip_len is 829 * shorter than the difference (max_split_len pivot is not covered by this 830 * node but covered by its parent, the best we can do is split at the branch 831 * lead to this node. we insert a skip_len=0 node and use it as split point 832 */ 833 (*split_node)->skip_len = 0; 834 (*split_node)->skip_addr = 0; 835 836 if (_BITGET(trie->skip_addr, (trie->skip_len-1))) { 837 (*split_node)->child[1] = trie; 838 } else { 839 (*split_node)->child[0] = trie; 840 } 841 842 /* the split point is with length max_split_len */ 843 *length -= trie->skip_len; 844 845 /* update the current node to reflect the node inserted */ 846 trie->skip_len = trie->skip_len - 1; 847 } else { 848 /* the length is longer than the max_split_len, and the trie->skip_len is 849 * longer than the difference (max_split_len pivot is covered by this 850 * node, we insert a node with length = max_split_len and use it as split point 851 */ 852 (*split_node)->skip_len = trie->skip_len - (*length - max_split_len); 853 (*split_node)->skip_addr = (trie->skip_addr >> (*length - max_split_len)); 854 855 if (_BITGET(trie->skip_addr, (*length-max_split_len-1))) { 856 (*split_node)->child[1] = trie; 857 } else { 858 (*split_node)->child[0] = trie; 859 } 860 861 /* update the current node to reflect the node inserted */ 862 trie->skip_len = *length - max_split_len - 1; 863 864 /* the split point is with length max_split_len */ 865 *length = max_split_len; 866 } 867 868 trie->skip_addr = trie->skip_addr & BITMASK(trie->skip_len); 869 870 /* there is no need to update the parent node's child pointer 871 * to the "trie" node since we will split here and the parent node's 872 * child pointer will be set to NULL later 873 */ 874 *split_count = trie->count; 875 876 if (SOC_SUCCESS(rv)) { 877 rv = taps_key_shift(pivot, *length+trie->skip_len+1, trie->skip_len+1); 878 } 879 *state = trieSplitStatePruneNodes; 880 return rv; 881 } 882 } else if ( ((*length == max_split_len) && (trie->count != max_count) && (trie->count <= max_split_count)) || 883 _alpm_lib_trie_v6_splitable(trie, trie->child[bit], cb, user_data, max_count, max_split_count)) { 884 /* 885 * (1) when the node is at the max_split_len and if used as spliting point 886 * the resulted trie will not have all pivots (FULL). we should split 887 * at this node. 888 * (2) when the node is at the max_split_len and if the resulted trie 889 * will have all pivots (FULL), we fall through to keep searching 890 * (3) when the node is shorter than the max_split_len and the node 891 * has a more even pivot distribution compare to it's cc, we 892 * can split at this node. The split count must be less than or 893 * equal to max_split_count. 894 * (4) when the node's count is only 1, we must split at this point. 895 * 896 * NOTE: 897 * when trie->count == max_count, the above check will be FALSE 898 * so here it guarrantees *length < max_split_len. We don't 899 * need to further split this node. 900 */ 901 *split_node = trie; 902 *split_count = trie->count; 903 904 if ((trieSplitStatePayloadSplit == *state) && 905 (trie->type == trieNodeTypeInternal)) { 906 *state = trieSplitStatePayloadSplitDone; 907 } else { 908 *state = trieSplitStatePruneNodes; 909 return rv; 910 } 911 } else { 912 /* we can not split at this node, keep searching, it's better to 913 * split at longer pivot 914 */ 915 rv = _key_append(pivot, length, bit, 1); 916 if (SOC_FAILURE(rv)) return rv; 917 918 rv = _alpm_lib_trie_v6_split(trie->child[bit], 919 pivot, length, 920 split_count, split_node, 921 child, max_count, max_split_len, 922 state, cb, user_data, max_split_count); 923 } 924 925 /* free up internal nodes if applicable */ 926 switch(*state) { 927 case trieSplitStatePayloadSplitDone: 928 if (trie->type == trieNodeTypePayload) { 929 *state = trieSplitStatePruneNodes; 930 *split_node = trie; 931 *split_count = trie->count; 932 } else { 933 /* shift the pivot to right to ignore this internal node */ 934 rv = taps_key_shift(pivot, *length, trie->skip_len+1); 935 assert(*length >= trie->skip_len + 1); 936 *length -= (trie->skip_len + 1); 937 } 938 break; 939 940 case trieSplitStatePruneNodes: 941 if (trie->count == *split_count) { 942 /* if the split point has associate internal nodes they have to 943 * be cleaned up */ 944 assert(trie->type == trieNodeTypeInternal); 945 assert(!(trie->child[0] && trie->child[1])); 946 alpm_util_free(trie); 947 } else { 948 assert(*child == NULL); 949 /* fuse with child if possible */ 950 trie->child[bit] = NULL; 951 bit = (bit==0)?1:0; 952 trie->count -= *split_count; 953 954 /* optimize more */ 955 if ((trie->type == trieNodeTypeInternal) && 956 (trie->skip_len + 957 trie->child[bit]->skip_len + 1 <= _MAX_SKIP_LEN_)) { 958 *child = trie->child[bit]; 959 rv = _alpm_lib_trie_fuse_child(trie, bit); 960 if (rv != SOC_E_NONE) { 961 *child = NULL; 962 } 963 } 964 *state = trieSplitStateDone; 965 } 966 break; 967 968 case trieSplitStateDone: 969 /* adjust parent's count */ 970 assert(*split_count > 0); 971 assert(trie->count >= *split_count); 972 973 /* update the child pointer if child was pruned */ 974 if (*child != NULL) { 975 trie->child[bit] = *child; 976 *child = NULL; 977 } 978 trie->count -= *split_count; 979 break; 980 981 default: 982 break; 983 } 984 985 return rv; 986 } 987 988 989 990 /* 991 * Function: 992 * _alpm_lib_trie_v6_merge 993 * Purpose: 994 * merge or fuse the child trie with parent trie 995 */ 996 int 997 _alpm_lib_trie_v6_merge(alpm_lib_trie_node_t *parent_trie, 998 alpm_lib_trie_node_t *child_trie, 999 uint32 *pivot, 1000 uint32 length, 1001 alpm_lib_trie_node_t **new_parent) 1002 { 1003 int rv, child_count; 1004 alpm_lib_trie_node_t *child = NULL, clone; 1005 uint32 child_pivot[BITS2WORDS(_MAX_KEY_LEN_144_)] = {0}; 1006 uint32 child_length = 0; 1007 1008 /* 1009 * to do merge, there is one and only one condition: 1010 * parent must cover the child 1011 */ 1012 1013 /* 1014 * child pivot could be an internal node, i.e., NOT_FOUND on search 1015 * so check the out child instead of rv. 1016 */ 1017 _alpm_lib_trie_v6_search(child_trie, pivot, length, &child, child_pivot, &child_length, 0, 1); 1018 if (child == NULL) { 1019 return SOC_E_PARAM; 1020 } 1021 1022 _TRIE_NODE_CLONE_(&clone, child); 1023 1024 if (child != child_trie) { 1025 rv = _alpm_lib_trie_v6_skip_node_free(child_trie, child_pivot, child_length); 1026 if (rv < 0) { 1027 return SOC_E_PARAM; 1028 } 1029 } 1030 1031 /* Record the child count before being cleared */ 1032 child_count = child->count; 1033 1034 /* Clear the info before insert, mainly it is to prevent previous non-zero 1035 * count being erroneously included to calculation. 1036 */ 1037 sal_memset(child, 0, sizeof(*child)); 1038 /* merge happens on bucket trie */ 1039 rv = _alpm_lib_trie_v6_insert(parent_trie, child_pivot, child_length, child, 1040 new_parent, child_count); 1041 if (rv < 0) { 1042 return SOC_E_PARAM; 1043 } 1044 1045 /* 1046 * child node, the inserted node, will be modified during insert, 1047 * and it must be a leaf node of the parent trie without any child. 1048 * The child node could be either payload or internal. 1049 */ 1050 if (child->child[0] || child->child[1]) { 1051 return SOC_E_PARAM; 1052 } 1053 if (clone.type == trieNodeTypeInternal) { 1054 child->type = trieNodeTypeInternal; 1055 } 1056 child->child[0] = clone.child[0]; 1057 child->child[1] = clone.child[1]; 1058 1059 return SOC_E_NONE; 1060 } 1061 1062 1063 1064 1065 /* 1066 * Function: 1067 * _alpm_lib_trie_v6_split2 1068 * Purpose: 1069 * Split the trie into 2 such that the new sub trie covers given prefix/length. 1070 * NOTE: 1071 * key, key_len -- The given prefix/length 1072 * max_split_count -- The sub trie's max allowed count. 1073 */ 1074 int 1075 _alpm_lib_trie_v6_split2(alpm_lib_trie_node_t *trie, 1076 uint32 *key, 1077 uint32 key_len, 1078 uint32 *pivot, 1079 uint32 *pivot_len, 1080 uint32 *split_count, 1081 alpm_lib_trie_node_t **split_node, 1082 alpm_lib_trie_node_t **child, 1083 alpm_lib_trie_split2_state_t *state, 1084 const int max_split_count, 1085 const int exact_same) 1086 { 1087 uint32 lcp=0; 1088 int bit=0, rv=SOC_E_NONE; 1089 1090 /* start building the pivot */ 1091 rv = _key_append(pivot, pivot_len, trie->skip_addr, trie->skip_len); 1092 if (SOC_FAILURE(rv)) return rv; 1093 1094 1095 lcp = lcplen(key, key_len, trie->skip_addr, trie->skip_len); 1096 1097 if (lcp == trie->skip_len) { 1098 if (trie->count <= max_split_count && 1099 (!exact_same || (key_len - lcp) == 0)) { 1100 *split_node = trie; 1101 *split_count = trie->count; 1102 if (trie->count < max_split_count) { 1103 *state = trieSplit2StatePruneNodes; 1104 } 1105 return SOC_E_NONE; 1106 } 1107 if (key_len > lcp) { 1108 bit = (key[KEY144_BIT2IDX(key_len - lcp)] & \ 1109 (1 << ((key_len - lcp - 1) % _NUM_WORD_BITS_))) ? 1:0; 1110 1111 /* based on next bit branch left or right */ 1112 if (trie->child[bit]) { 1113 /* we can not split at this node, keep searching, it's better to 1114 * split at longer pivot 1115 */ 1116 rv = _key_append(pivot, pivot_len, bit, 1); 1117 if (SOC_FAILURE(rv)) return rv; 1118 1119 rv = _alpm_lib_trie_v6_split2(trie->child[bit], 1120 key, key_len - lcp - 1, 1121 pivot, pivot_len, split_count, 1122 split_node, child, state, 1123 max_split_count, exact_same); 1124 if (SOC_FAILURE(rv)) return rv; 1125 } 1126 } 1127 } 1128 1129 /* free up internal nodes if applicable */ 1130 switch(*state) { 1131 case trieSplit2StateNone: /* fail to split */ 1132 break; 1133 1134 case trieSplit2StatePruneNodes: 1135 if (trie->count == *split_count) { 1136 /* if the split point has associate internal nodes they have to 1137 * be cleaned up */ 1138 assert(trie->type == trieNodeTypeInternal); 1139 /* at most one child */ 1140 assert(!(trie->child[0] && trie->child[1])); 1141 /* at least one child */ 1142 assert(trie->child[0] || trie->child[1]); 1143 alpm_util_free(trie); 1144 } else { 1145 assert(*child == NULL); 1146 /* fuse with child if possible */ 1147 trie->child[bit] = NULL; 1148 bit = (bit==0)?1:0; 1149 trie->count -= *split_count; 1150 1151 /* optimize more */ 1152 if ((trie->type == trieNodeTypeInternal) && 1153 (trie->skip_len + 1154 trie->child[bit]->skip_len + 1 <= _MAX_SKIP_LEN_)) { 1155 *child = trie->child[bit]; 1156 rv = _alpm_lib_trie_fuse_child(trie, bit); 1157 if (rv != SOC_E_NONE) { 1158 *child = NULL; 1159 } 1160 } 1161 *state = trieSplit2StateDone; 1162 } 1163 break; 1164 1165 case trieSplit2StateDone: 1166 /* adjust parent's count */ 1167 assert(*split_count > 0); 1168 assert(trie->count >= *split_count); 1169 1170 /* update the child pointer if child was pruned */ 1171 if (*child != NULL) { 1172 trie->child[bit] = *child; 1173 *child = NULL; 1174 } 1175 trie->count -= *split_count; 1176 break; 1177 1178 default: 1179 break; 1180 } 1181 1182 return rv; 1183 } 1184 1185 /* 1186 * Function: 1187 * _alpm_lib_trie_v6_ppg_prefix_validate 1188 * Purpose: 1189 * validate that the provided prefix is valid for propagation. 1190 * The added prefix which was member of a shorter pivot's domain 1191 * must never be more specific than another pivot encounter if any 1192 * in the path 1193 */ 1194 STATIC int _alpm_lib_trie_v6_ppg_prefix_validate(alpm_lib_trie_node_t *trie, 1195 uint32 *pfx, 1196 uint32 len) 1197 { 1198 uint32 lcp=0, bit=0; 1199 1200 if (len == 0) return SOC_E_NONE; 1201 1202 lcp = lcplen(pfx, len, trie->skip_addr, trie->skip_len); 1203 1204 if (lcp == trie->skip_len) { 1205 if (trieNodeTypePayload == trie->type) { 1206 return SOC_E_PARAM; 1207 } 1208 1209 if (len == lcp) { 1210 return SOC_E_NONE; 1211 } 1212 1213 bit = _alpm_lib_key_get_bits(pfx, len-lcp, 1); 1214 if (!trie->child[bit]) { 1215 return SOC_E_NONE; 1216 } 1217 1218 return _alpm_lib_trie_v6_ppg_prefix_validate(trie->child[bit], 1219 pfx, len-1-lcp); 1220 } 1221 1222 return SOC_E_NONE; 1223 } 1224 1225 /* 1226 * Function: 1227 * _alpm_lib_trie_v6_ppg_prefix_walk 1228 * Purpose: 1229 * If the propogation starts from intermediate pivot on 1230 * the trie, then the prefix length has to be appropriately adjusted or else 1231 * it will end up with ill updates. 1232 * Assumption: the prefix length is adjusted as per trie node on 1233 * which is starts from. 1234 * If node == head node then adjust is none 1235 * node == pivot, then prefix length = org len - pivot len 1236 */ 1237 int _alpm_lib_trie_v6_ppg_prefix_walk(alpm_lib_trie_node_t *trie, 1238 uint32 *pfx, 1239 uint32 len, 1240 alpm_lib_trie_ppg_cb_f cb, 1241 alpm_lib_trie_bpm_cb_info_t *cb_info) 1242 { 1243 int rv = SOC_E_NONE; 1244 uint32 bit=0, lcp=0; 1245 1246 if (!trie || (len && trie->skip_len && !pfx) || 1247 (len > _MAX_KEY_LEN_144_) || !cb || !cb_info) { 1248 return SOC_E_PARAM; 1249 } 1250 1251 if (len > 0) { 1252 lcp = lcplen(pfx, len, trie->skip_addr, trie->skip_len); 1253 /* if the lcp is less than prefix length the prefix is not applicable 1254 * for any propagation */ 1255 if (lcp < ((len>trie->skip_len) ? trie->skip_len : len)) { 1256 return SOC_E_NONE; 1257 } else { 1258 if (len > trie->skip_len) { 1259 bit = _alpm_lib_key_get_bits(pfx, len-lcp, 1); 1260 if (!trie->child[bit]) { 1261 return SOC_E_NONE; 1262 } 1263 rv = _alpm_lib_trie_v6_ppg_prefix_walk(trie->child[bit], 1264 pfx, len-lcp-1, cb, cb_info); 1265 } else { 1266 /* pfx is <= trie skip len */ 1267 rv = _trie_traverse_ppg_prefix(trie, cb, cb_info); 1268 if (SOC_E_LIMIT == rv) { 1269 rv = SOC_E_NONE; 1270 } 1271 } 1272 } 1273 } else { 1274 rv = _trie_traverse_ppg_prefix(trie, cb, cb_info); 1275 if (SOC_E_LIMIT == rv) { 1276 rv = SOC_E_NONE; 1277 } 1278 } 1279 1280 return rv; 1281 } 1282 1283 /* 1284 * Function: 1285 * _alpm_lib_trie_v6_ppg_prefix 1286 * Purpose: 1287 * Propogate prefix from a given pivot. 1288 * Callback function to decide INSERT/DELETE propagation, 1289 * and decide to update bpm_len or not. 1290 */ 1291 int _alpm_lib_trie_v6_ppg_prefix(alpm_lib_trie_node_t *pivot, 1292 uint32 pivot_len, 1293 uint32 *pfx, 1294 uint32 len, 1295 alpm_lib_trie_ppg_cb_f cb, 1296 alpm_lib_trie_bpm_cb_info_t *cb_info) 1297 { 1298 int rv = SOC_E_NONE; 1299 1300 len -= pivot_len; 1301 1302 if (len > 0) { 1303 uint32 bit = _alpm_lib_key_get_bits(pfx, len, 1); 1304 1305 if (pivot->child[bit]) { 1306 /* validate if the pivot provided is correct */ 1307 rv = _alpm_lib_trie_v6_ppg_prefix_validate( 1308 pivot->child[bit], pfx, len-1); 1309 if (SOC_SUCCESS(rv)) { 1310 rv = _alpm_lib_trie_v6_ppg_prefix_walk( 1311 pivot->child[bit], 1312 pfx, len-1, cb, cb_info); 1313 } 1314 } /* else nop, nothing to propagate on this path end */ 1315 } else { 1316 /* pivot == prefix */ 1317 rv = _alpm_lib_trie_v6_ppg_prefix_walk( 1318 pivot, pfx, pivot->skip_len, cb, cb_info); 1319 } 1320 1321 return rv; 1322 } 1323 1324 #endif /* ALPM_ENABLE */ 1325