drivers/net/npe/IxEthDBPortUpdate.c

   1 /**
   2  * @file IxEthDBDBPortUpdate.c
   3  *
   4  * @brief Implementation of dependency and port update handling
   5  *
   6  * @par
   7  * IXP400 SW Release version 2.0
   8  *
   9  * -- Copyright Notice --
  10  *
  11  * @par
  12  * Copyright 2001-2005, Intel Corporation.
  13  * All rights reserved.
  14  *
  15  * @par
  16  * SPDX-License-Identifier:     BSD-3-Clause
  17  * @par
  18  * -- End of Copyright Notice --
  19  */
  20
  21 #include "IxEthDB_p.h"
  22
  23 /* forward prototype declarations */
  24 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor);
  25 IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
  26 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
  27 IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size);
  28 IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
  29 IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
  30 IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);
  31
  32 extern HashTable dbHashtable;
  33
  34 /**
  35  * @brief register types requiring automatic updates
  36  *
  37  * @param typeArray array indexed on record types, each
  38  * element indicating whether the record type requires an
  39  * automatic update (true) or not (false)
  40  *
  41  * Automatic updates are done for registered record types
  42  * upon adding, updating (that is, updating the record portID)
  43  * and removing records. Whenever an automatic update is triggered
  44  * the appropriate ports will be provided with new database
  45  * information.
  46  *
  47  * It is assumed that the typeArray parameter is allocated large
  48  * enough to hold all the user defined types. Also, the type
  49  * array should be initialized to false as this function only
  50  * caters for types which do require automatic updates.
  51  *
  52  * Note that this function should be called by the component
  53  * initialization function.
  54  *
  55  * @return number of record types registered for automatic
  56  * updates
  57  *
  58  * @internal
  59  */
  60 IX_ETH_DB_PUBLIC
  61 UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
  62 {
  63     typeArray[IX_ETH_DB_FILTERING_RECORD]      = true;
  64     typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true;
  65
  66     return 2;
  67 }
  68
  69 /**
  70  * @brief computes dependencies and triggers port learning tree updates
  71  *
  72  * @param triggerPorts port map consisting in the ports which triggered the update
  73  *
  74  * This function browses through all the ports and determines how to waterfall the update
  75  * event from the trigger ports to all other ports depending on them.
  76  *
  77  * Once the list of ports to be updated is determined this function
  78  * calls @ref ixEthDBCreateTrees.
  79  *
  80  * @internal
  81  */
  82 IX_ETH_DB_PUBLIC
  83 void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts)
  84 {
  85     IxEthDBPortMap updatePorts;
  86     UINT32 portIndex;
  87
  88     ixEthDBUpdateLock();
  89
  90     SET_EMPTY_DEPENDENCY_MAP(updatePorts);
  91
  92     for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
  93     {
  94         PortInfo *port   = &ixEthDBPortInfo[portIndex];
  95         BOOL mapsCollide;
  96
  97         MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap);
  98
  99         if (mapsCollide                                   /* do triggers influence this port? */
 100             && !IS_PORT_INCLUDED(portIndex, updatePorts)  /* and it's not already in the update list */
 101             && port->updateMethod.updateEnabled)          /* and we're allowed to update it */
 102         {
 103             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex);
 104
 105             JOIN_PORT_TO_MAP(updatePorts, portIndex);
 106         }
 107         else
 108         {
 109             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex);
 110
 111             if (!mapsCollide)
 112             {
 113                 IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex);
 114             }
 115
 116             if (IS_PORT_INCLUDED(portIndex, updatePorts))
 117             {
 118                 IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex);
 119             }
 120
 121             if (!port->updateMethod.updateEnabled)
 122             {
 123                 IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex);
 124             }
 125         }
 126     }
 127
 128     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n");
 129
 130     ixEthDBCreateTrees(updatePorts);
 131
 132     ixEthDBUpdateUnlock();
 133 }
 134
 135 /**
 136  * @brief creates learning trees and calls the port update handlers
 137  *
 138  * @param updatePorts set of ports in need of learning trees
 139  *
 140  * This function determines the optimal method of creating learning
 141  * trees using a minimal number of database queries, keeping in mind
 142  * that different ports can either use the same learning trees or they
 143  * can partially share them. The actual tree building routine is
 144  * @ref ixEthDBQuery.
 145  *
 146  * @internal
 147  */
 148 IX_ETH_DB_PRIVATE
 149 void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
 150 {
 151     UINT32 portIndex;
 152     BOOL result;
 153     BOOL portsLeft = true;
 154
 155     while (portsLeft)
 156     {
 157         /* get port with minimal dependency map and NULL search tree */
 158         UINT32 minPortIndex = MAX_PORT_SIZE;
 159         UINT32 minimalSize  = MAX_PORT_SIZE;
 160
 161         for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
 162         {
 163             UINT32 size;
 164             PortInfo *port = &ixEthDBPortInfo[portIndex];
 165
 166             /* generate trees only for ports that need them */
 167             if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts))
 168             {
 169                 GET_MAP_SIZE(port->dependencyPortMap, size);
 170
 171                 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n",
 172                     portIndex, size);
 173
 174                 if (size < minimalSize)
 175                 {
 176                     minPortIndex = portIndex;
 177                     minimalSize  = size;
 178                 }
 179             }
 180             else
 181             {
 182                 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex,
 183                     port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query");
 184             }
 185         }
 186
 187         /* if a port was found than minimalSize is not MAX_PORT_SIZE */
 188         if (minimalSize != MAX_PORT_SIZE)
 189         {
 190             /* minPortIndex is the port we seek */
 191             PortInfo *port = &ixEthDBPortInfo[minPortIndex];
 192
 193             IxEthDBPortMap query;
 194             MacTreeNode *baseTree;
 195
 196             /* now try to find a port with minimal map difference */
 197             PortInfo *minimalDiffPort = NULL;
 198             UINT32 minimalDiff        = MAX_PORT_SIZE;
 199
 200             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex);
 201
 202             for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
 203             {
 204                 PortInfo *diffPort = &ixEthDBPortInfo[portIndex];
 205                 BOOL mapIsSubset;
 206
 207                 IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap);
 208
 209
 210                 if (portIndex != minPortIndex
 211                     && diffPort->updateMethod.searchTree != NULL
 212                     && mapIsSubset)
 213                 {
 214                     /* compute size and pick only minimal size difference */
 215                     UINT32 diffPortSize;
 216                     UINT32 sizeDifference;
 217
 218                     GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize);
 219
 220                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex);
 221
 222                     sizeDifference = minimalSize - diffPortSize;
 223
 224                     if (sizeDifference < minimalDiff)
 225                     {
 226                         minimalDiffPort = diffPort;
 227                         minimalDiff     = sizeDifference;
 228
 229                         IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n",
 230                             minimalDiff, portIndex);
 231                     }
 232                 }
 233             }
 234
 235             /* check if filtering is enabled on this port */
 236             if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0)
 237             {
 238                 /* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */
 239                 if (minimalDiff != MAX_PORT_SIZE)
 240                 {
 241                     baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree);
 242                     DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap);
 243
 244                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n",
 245                         minimalDiffPort->portID);
 246                 }
 247                 else /* .. otherwise no similar port was found, build tree from scratch */
 248                 {
 249                     baseTree = NULL;
 250
 251                     COPY_DEPENDENCY_MAP(query, port->dependencyPortMap);
 252
 253                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n");
 254                 }
 255
 256                 IS_EMPTY_DEPENDENCY_MAP(result, query);
 257
 258                 if (!result) /* otherwise we don't need anything more on top of the cloned tree */
 259                 {
 260                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex);
 261
 262                     /* build learning tree */
 263                     port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE);
 264                 }
 265                 else
 266                 {
 267                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n");
 268
 269                     port->updateMethod.searchTree = baseTree;
 270                 }
 271             }
 272             else
 273             {
 274                 /* filtering is not enabled, will download an empty tree */
 275                 if (port->updateMethod.searchTree != NULL)
 276                 {
 277                     ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
 278                 }
 279
 280                 port->updateMethod.searchTree = NULL;
 281             }
 282
 283             /* mark tree as valid */
 284             port->updateMethod.searchTreePendingWrite = true;
 285         }
 286         else
 287         {
 288             portsLeft = false;
 289
 290             IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n");
 291         }
 292     }
 293
 294     for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
 295     {
 296         PortInfo *updatePort = &ixEthDBPortInfo[portIndex];
 297
 298         if (updatePort->updateMethod.searchTreePendingWrite)
 299         {
 300             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n",
 301                 updatePort->updateMethod.searchTree != NULL ? "not " : "",
 302                 portIndex);
 303
 304             updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD);
 305         }
 306     }
 307 }
 308
 309 /**
 310  * @brief standard NPE update handler
 311  *
 312  * @param portID id of the port to be updated
 313  * @param type record type to be pushed during this update
 314  *
 315  * The NPE update handler manages updating the NPE databases
 316  * given a certain record type.
 317  *
 318  * @internal
 319  */
 320 IX_ETH_DB_PUBLIC
 321 IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type)
 322 {
 323     UINT32 epDelta, blockCount;
 324     IxNpeMhMessage message;
 325     UINT32 treeSize = 0;
 326     PortInfo *port = &ixEthDBPortInfo[portID];
 327
 328     /* size selection and type check */
 329     if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
 330     {
 331         treeSize = FULL_ELT_BYTE_SIZE;
 332     }
 333     else if (type == IX_ETH_DB_FIREWALL_RECORD)
 334     {
 335         treeSize = FULL_FW_BYTE_SIZE;
 336     }
 337     else
 338     {
 339         return IX_ETH_DB_INVALID_ARG;
 340     }
 341
 342     /* serialize tree into memory */
 343     ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount);
 344
 345     /* free internal copy */
 346     if (port->updateMethod.searchTree != NULL)
 347     {
 348         ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
 349     }
 350
 351     /* forget last used search tree */
 352     port->updateMethod.searchTree             = NULL;
 353     port->updateMethod.searchTreePendingWrite = false;
 354
 355     /* dependending on the update type we do different things */
 356     if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
 357     {
 358         IX_STATUS result;
 359
 360         FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),
 361             epDelta, blockCount,
 362             IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));
 363
 364         IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);
 365
 366         if (result == IX_SUCCESS)
 367         {
 368             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);
 369         }
 370         else
 371         {
 372             ixEthDBPortInfo[portID].agingEnabled                = false;
 373             ixEthDBPortInfo[portID].updateMethod.updateEnabled  = false;
 374             ixEthDBPortInfo[portID].updateMethod.userControlled = true;
 375
 376             ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);
 377
 378             ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);
 379
 380             return IX_ETH_DB_FAIL;
 381         }
 382
 383         return IX_ETH_DB_SUCCESS;
 384     }
 385     else if (type == IX_ETH_DB_FIREWALL_RECORD)
 386     {
 387         return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);
 388     }
 389
 390     return IX_ETH_DB_INVALID_ARG;
 391 }
 392
 393 /**
 394  * @brief queries the database for a set of records to be inserted into a given tree
 395  *
 396  * @param searchTree pointer to a tree where insertions will be performed; can be NULL
 397  * @param query set of ports that a database record must match to be inserted into the tree
 398  *
 399  * The query method browses through the database, extracts all the descriptors matching
 400  * the given query parameter and inserts them into the given learning tree.
 401  * Note that this is an append procedure, the given tree needs not to be empty.
 402  * A "descriptor matching the query" is a descriptor whose port id is in the query map.
 403  * If the given tree is empty (NULL) a new tree is created and returned.
 404  *
 405  * @return the tree root
 406  *
 407  * @internal
 408  */
 409 IX_ETH_DB_PUBLIC
 410 MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries)
 411 {
 412     HashIterator iterator;
 413     UINT32 entryCount = 0;
 414
 415     /* browse database */
 416     BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));
 417
 418     while (IS_ITERATOR_VALID(&iterator))
 419     {
 420         MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data;
 421
 422         IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",
 423             mac2string(descriptor->macAddress),
 424             descriptor->portID);
 425
 426         if ((descriptor->type & recordFilter) != 0
 427             && IS_PORT_INCLUDED(descriptor->portID, query))
 428         {
 429             MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);
 430
 431             IX_ETH_DB_UPDATE_TRACE("match\n");
 432
 433             if (descriptorClone != NULL)
 434             {
 435                 /* add descriptor to tree */
 436                 searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);
 437
 438                 entryCount++;
 439             }
 440         }
 441         else
 442         {
 443             IX_ETH_DB_UPDATE_TRACE("no match\n");
 444         }
 445
 446         if (entryCount < maxEntries)
 447         {
 448             /* advance to the next record */
 449                 BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));
 450         }
 451         else
 452         {
 453             /* the NPE won't accept more entries so we can stop now */
 454             ixEthDBReleaseHashIterator(&iterator);
 455
 456             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");
 457
 458             break;
 459         }
 460     }
 461
 462     IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);
 463
 464     return ixEthDBTreeRebalance(searchTree);
 465 }
 466
 467 /**
 468  * @brief inserts a mac descriptor into an tree
 469  *
 470  * @param searchTree tree where the insertion is to be performed (may be NULL)
 471  * @param descriptor descriptor to insert into tree
 472  *
 473  * @return the tree root
 474  *
 475  * @internal
 476  */
 477 IX_ETH_DB_PRIVATE
 478 MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor)
 479 {
 480     MacTreeNode *currentNode    = searchTree;
 481     MacTreeNode *insertLocation = NULL;
 482     MacTreeNode *newNode;
 483     INT32 insertPosition = RIGHT;
 484
 485     if (descriptor == NULL)
 486     {
 487         return searchTree;
 488     }
 489
 490     /* create a new node */
 491     newNode = ixEthDBAllocMacTreeNode();
 492
 493     if (newNode == NULL)
 494     {
 495         /* out of memory */
 496         ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);
 497
 498         ixEthDBFreeMacDescriptor(descriptor);
 499
 500         return NULL;
 501     }
 502
 503     /* populate node */
 504     newNode->descriptor = descriptor;
 505
 506     /* an empty initial tree is a special case */
 507     if (searchTree == NULL)
 508     {
 509         return newNode;
 510     }
 511
 512     /* get insertion location */
 513     while (insertLocation == NULL)
 514     {
 515         MacTreeNode *nextNode;
 516
 517         /* compare given key with current node key */
 518         insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);
 519
 520         /* navigate down */
 521         if (insertPosition == RIGHT)
 522         {
 523             nextNode = currentNode->right;
 524         }
 525         else if (insertPosition == LEFT)
 526         {
 527             nextNode = currentNode->left;
 528         }
 529         else
 530         {
 531             /* error, duplicate key */
 532             ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");
 533
 534             /* this will free the MAC descriptor as well */
 535             ixEthDBFreeMacTreeNode(newNode);
 536
 537             return searchTree;
 538         }
 539
 540         /* when we can no longer dive through the tree we found the insertion place */
 541         if (nextNode != NULL)
 542         {
 543             currentNode = nextNode;
 544         }
 545         else
 546         {
 547             insertLocation = currentNode;
 548         }
 549     }
 550
 551     /* insert node */
 552     if (insertPosition == RIGHT)
 553     {
 554         insertLocation->right = newNode;
 555     }
 556     else
 557     {
 558         insertLocation->left = newNode;
 559     }
 560
 561     return searchTree;
 562 }
 563
 564 /**
 565  * @brief balance a tree
 566  *
 567  * @param searchTree tree to balance
 568  *
 569  * Converts a tree into a balanced tree and returns the root of
 570  * the balanced tree. The resulting tree is <i>route balanced</i>
 571  * not <i>perfectly balanced</i>. This makes no difference to the
 572  * average tree search time which is the same in both cases, O(log2(n)).
 573  *
 574  * @return root of the balanced tree or NULL if there's no memory left
 575  *
 576  * @internal
 577  */
 578 IX_ETH_DB_PRIVATE
 579 MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree)
 580 {
 581     MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();
 582     UINT32 size;
 583
 584     if (pseudoRoot == NULL)
 585     {
 586         /* out of memory */
 587         return NULL;
 588     }
 589
 590     pseudoRoot->right = searchTree;
 591
 592     ixEthDBRebalanceTreeToVine(pseudoRoot, &size);
 593     ixEthDBRebalanceVineToTree(pseudoRoot, size);
 594
 595     searchTree = pseudoRoot->right;
 596
 597     /* remove pseudoRoot right branch, otherwise it will free the entire tree */
 598     pseudoRoot->right = NULL;
 599
 600     ixEthDBFreeMacTreeNode(pseudoRoot);
 601
 602     return searchTree;
 603 }
 604
 605 /**
 606  * @brief converts a tree into a vine
 607  *
 608  * @param root root of tree to convert
 609  * @param size depth of vine (equal to the number of nodes in the tree)
 610  *
 611  * @internal
 612  */
 613 IX_ETH_DB_PRIVATE
 614 void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size)
 615 {
 616     MacTreeNode *vineTail  = root;
 617     MacTreeNode *remainder = vineTail->right;
 618     MacTreeNode *tempPtr;
 619
 620     *size = 0;
 621
 622     while (remainder != NULL)
 623     {
 624         if (remainder->left == NULL)
 625         {
 626             /* move tail down one */
 627             vineTail  = remainder;
 628             remainder = remainder->right;
 629             (*size)++;
 630         }
 631         else
 632         {
 633             /* rotate around remainder */
 634             tempPtr         = remainder->left;
 635             remainder->left = tempPtr->right;
 636             tempPtr->right  = remainder;
 637             remainder       = tempPtr;
 638             vineTail->right = tempPtr;
 639         }
 640     }
 641 }
 642
 643 /**
 644  * @brief converts a vine into a balanced tree
 645  *
 646  * @param root vine to convert
 647  * @param size depth of vine
 648  *
 649  * @internal
 650  */
 651 IX_ETH_DB_PRIVATE
 652 void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size)
 653 {
 654     UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));
 655
 656     ixEthDBRebalanceCompression(root, leafCount);
 657
 658     size = size - leafCount;
 659
 660     while (size > 1)
 661     {
 662         ixEthDBRebalanceCompression(root, size / 2);
 663
 664         size /= 2;
 665     }
 666 }
 667
 668 /**
 669  * @brief compresses a vine/tree stage into a more balanced vine/tree
 670  *
 671  * @param root root of the tree to compress
 672  * @param count number of "spine" nodes
 673  *
 674  * @internal
 675  */
 676 IX_ETH_DB_PRIVATE
 677 void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count)
 678 {
 679     MacTreeNode *scanner = root;
 680     MacTreeNode *child;
 681     UINT32 local_index;
 682
 683     for (local_index = 0 ; local_index < count ; local_index++)
 684     {
 685         child          = scanner->right;
 686         scanner->right = child->right;
 687         scanner        = scanner->right;
 688         child->right   = scanner->left;
 689         scanner->left  = child;
 690     }
 691 }
 692
 693 /**
 694  * @brief computes |_log2(x)_| (a.k.a. floor(log2(x)))
 695  *
 696  * @param x number to compute |_log2(x)_| for
 697  *
 698  * @return |_log2(x)_|
 699  *
 700  * @internal
 701  */
 702 IX_ETH_DB_PRIVATE
 703 UINT32 ixEthDBRebalanceLog2Floor(UINT32 x)
 704 {
 705     UINT32 log = 0;
 706     UINT32 val = 1;
 707
 708     while (val < x)
 709     {
 710         log++;
 711         val <<= 1;
 712     }
 713
 714     return val == x ? log : log - 1;
 715 }
 716