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