drivers/net/npe/IxEthDBPortUpdate.c - github/trini/u-boot - Gitiles

 /**
  * @file IxEthDBDBPortUpdate.c
  *
  * @brief Implementation of dependency and port update handling
  *
  * @par
  * IXP400 SW Release version 2.0
  *
  * -- Copyright Notice --
  *
  * @par
  * Copyright 2001-2005, Intel Corporation.
  * All rights reserved.
  *
  * @par
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the Intel Corporation nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
  * @par
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
  * @par
  * -- End of Copyright Notice --
  */

 #include "IxEthDB_p.h"

 /* forward prototype declarations */
 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor);
 IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
 IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size);
 IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
 IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
 IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);

 extern HashTable dbHashtable;

 /**
  * @brief register types requiring automatic updates
  *
  * @param typeArray array indexed on record types, each
  * element indicating whether the record type requires an
  * automatic update (true) or not (false)
  *
  * Automatic updates are done for registered record types
  * upon adding, updating (that is, updating the record portID)
  * and removing records. Whenever an automatic update is triggered
  * the appropriate ports will be provided with new database
  * information.
  *
  * It is assumed that the typeArray parameter is allocated large
  * enough to hold all the user defined types. Also, the type
  * array should be initialized to false as this function only
  * caters for types which do require automatic updates.
  *
  * Note that this function should be called by the component
  * initialization function.
  *
  * @return number of record types registered for automatic
  * updates
  *
  * @internal
  */
 IX_ETH_DB_PUBLIC
 UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
 {
     typeArray[IX_ETH_DB_FILTERING_RECORD]      = true;
     typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true;

     return 2;
 }

 /**
  * @brief computes dependencies and triggers port learning tree updates
  *
  * @param triggerPorts port map consisting in the ports which triggered the update
  *
  * This function browses through all the ports and determines how to waterfall the update
  * event from the trigger ports to all other ports depending on them.
  *
  * Once the list of ports to be updated is determined this function
  * calls @ref ixEthDBCreateTrees.
  *
  * @internal
  */
 IX_ETH_DB_PUBLIC
 void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts)
 {
     IxEthDBPortMap updatePorts;
     UINT32 portIndex;

     ixEthDBUpdateLock();

     SET_EMPTY_DEPENDENCY_MAP(updatePorts);

     for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
     {
         PortInfo *port   = &ixEthDBPortInfo[portIndex];
         BOOL mapsCollide;

         MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap);

         if (mapsCollide                                   /* do triggers influence this port? */
             && !IS_PORT_INCLUDED(portIndex, updatePorts)  /* and it's not already in the update list */
             && port->updateMethod.updateEnabled)          /* and we're allowed to update it */
         {
             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex);

             JOIN_PORT_TO_MAP(updatePorts, portIndex);
         }
         else
         {
             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex);

             if (!mapsCollide)
             {
                 IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex);
             }

             if (IS_PORT_INCLUDED(portIndex, updatePorts))
             {
                 IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex);
             }

             if (!port->updateMethod.updateEnabled)
             {
                 IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex);
             }
         }
     }

     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n");

     ixEthDBCreateTrees(updatePorts);

     ixEthDBUpdateUnlock();
 }

 /**
  * @brief creates learning trees and calls the port update handlers
  *
  * @param updatePorts set of ports in need of learning trees
  *
  * This function determines the optimal method of creating learning
  * trees using a minimal number of database queries, keeping in mind
  * that different ports can either use the same learning trees or they
  * can partially share them. The actual tree building routine is
  * @ref ixEthDBQuery.
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
 {
     UINT32 portIndex;
     BOOL result;
     BOOL portsLeft = true;

     while (portsLeft)
     {
         /* get port with minimal dependency map and NULL search tree */
         UINT32 minPortIndex = MAX_PORT_SIZE;
         UINT32 minimalSize  = MAX_PORT_SIZE;

         for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
         {
             UINT32 size;
             PortInfo *port = &ixEthDBPortInfo[portIndex];

             /* generate trees only for ports that need them */
             if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts))
             {
                 GET_MAP_SIZE(port->dependencyPortMap, size);

                 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n",
                     portIndex, size);

                 if (size < minimalSize)
                 {
                     minPortIndex = portIndex;
                     minimalSize  = size;
                 }
             }
             else
             {
                 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex,
                     port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query");
             }
         }

         /* if a port was found than minimalSize is not MAX_PORT_SIZE */
         if (minimalSize != MAX_PORT_SIZE)
         {
             /* minPortIndex is the port we seek */
             PortInfo *port = &ixEthDBPortInfo[minPortIndex];

             IxEthDBPortMap query;
             MacTreeNode *baseTree;

             /* now try to find a port with minimal map difference */
             PortInfo *minimalDiffPort = NULL;
             UINT32 minimalDiff        = MAX_PORT_SIZE;

             IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex);

             for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
             {
                 PortInfo *diffPort = &ixEthDBPortInfo[portIndex];
                 BOOL mapIsSubset;

                 IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap);


                 if (portIndex != minPortIndex
                     && diffPort->updateMethod.searchTree != NULL
                     && mapIsSubset)
                 {
                     /* compute size and pick only minimal size difference */
                     UINT32 diffPortSize;
                     UINT32 sizeDifference;

                     GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize);

                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex);

                     sizeDifference = minimalSize - diffPortSize;

                     if (sizeDifference < minimalDiff)
                     {
                         minimalDiffPort = diffPort;
                         minimalDiff     = sizeDifference;

                         IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n",
                             minimalDiff, portIndex);
                     }
                 }
             }

             /* check if filtering is enabled on this port */
             if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0)
             {
                 /* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */
                 if (minimalDiff != MAX_PORT_SIZE)
                 {
                     baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree);
                     DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap);

                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n",
                         minimalDiffPort->portID);
                 }
                 else /* .. otherwise no similar port was found, build tree from scratch */
                 {
                     baseTree = NULL;

                     COPY_DEPENDENCY_MAP(query, port->dependencyPortMap);

                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n");
                 }

                 IS_EMPTY_DEPENDENCY_MAP(result, query);

                 if (!result) /* otherwise we don't need anything more on top of the cloned tree */
                 {
                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex);

                     /* build learning tree */
                     port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE);
                 }
                 else
                 {
                     IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n");

                     port->updateMethod.searchTree = baseTree;
                 }
             }
             else
             {
                 /* filtering is not enabled, will download an empty tree */
                 if (port->updateMethod.searchTree != NULL)
                 {
                     ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
                 }

                 port->updateMethod.searchTree = NULL;
             }

             /* mark tree as valid */
             port->updateMethod.searchTreePendingWrite = true;
         }
         else
         {
             portsLeft = false;

             IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n");
         }
     }

     for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
     {
         PortInfo *updatePort = &ixEthDBPortInfo[portIndex];

         if (updatePort->updateMethod.searchTreePendingWrite)
         {
             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n",
                 updatePort->updateMethod.searchTree != NULL ? "not " : "",
                 portIndex);

             updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD);
         }
     }
 }

 /**
  * @brief standard NPE update handler
  *
  * @param portID id of the port to be updated
  * @param type record type to be pushed during this update
  *
  * The NPE update handler manages updating the NPE databases
  * given a certain record type.
  *
  * @internal
  */
 IX_ETH_DB_PUBLIC
 IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type)
 {
     UINT32 epDelta, blockCount;
     IxNpeMhMessage message;
     UINT32 treeSize = 0;
     PortInfo *port = &ixEthDBPortInfo[portID];

     /* size selection and type check */
     if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
     {
         treeSize = FULL_ELT_BYTE_SIZE;
     }
     else if (type == IX_ETH_DB_FIREWALL_RECORD)
     {
         treeSize = FULL_FW_BYTE_SIZE;
     }
     else
     {
         return IX_ETH_DB_INVALID_ARG;
     }

     /* serialize tree into memory */
     ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount);

     /* free internal copy */
     if (port->updateMethod.searchTree != NULL)
     {
         ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
     }

     /* forget last used search tree */
     port->updateMethod.searchTree             = NULL;
     port->updateMethod.searchTreePendingWrite = false;

     /* dependending on the update type we do different things */
     if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
     {
         IX_STATUS result;

         FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),
             epDelta, blockCount,
             IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));

         IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);

         if (result == IX_SUCCESS)
 	{
             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);
         }
         else
         {
             ixEthDBPortInfo[portID].agingEnabled                = false;
             ixEthDBPortInfo[portID].updateMethod.updateEnabled  = false;
             ixEthDBPortInfo[portID].updateMethod.userControlled = true;

             ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);

             ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);

             return IX_ETH_DB_FAIL;
         }

 	return IX_ETH_DB_SUCCESS;
     }
     else if (type == IX_ETH_DB_FIREWALL_RECORD)
     {
         return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);
     }

     return IX_ETH_DB_INVALID_ARG;
 }

 /**
  * @brief queries the database for a set of records to be inserted into a given tree
  *
  * @param searchTree pointer to a tree where insertions will be performed; can be NULL
  * @param query set of ports that a database record must match to be inserted into the tree
  *
  * The query method browses through the database, extracts all the descriptors matching
  * the given query parameter and inserts them into the given learning tree.
  * Note that this is an append procedure, the given tree needs not to be empty.
  * A "descriptor matching the query" is a descriptor whose port id is in the query map.
  * If the given tree is empty (NULL) a new tree is created and returned.
  *
  * @return the tree root
  *
  * @internal
  */
 IX_ETH_DB_PUBLIC
 MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries)
 {
     HashIterator iterator;
     UINT32 entryCount = 0;

     /* browse database */
     BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));

     while (IS_ITERATOR_VALID(&iterator))
     {
         MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data;

         IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",
             mac2string(descriptor->macAddress),
             descriptor->portID);

 	if ((descriptor->type & recordFilter) != 0
             && IS_PORT_INCLUDED(descriptor->portID, query))
 	{
             MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);

             IX_ETH_DB_UPDATE_TRACE("match\n");

             if (descriptorClone != NULL)
             {
                 /* add descriptor to tree */
                 searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);

                 entryCount++;
             }
         }
         else
         {
             IX_ETH_DB_UPDATE_TRACE("no match\n");
         }

         if (entryCount < maxEntries)
         {
             /* advance to the next record */
 	        BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));
         }
         else
         {
             /* the NPE won't accept more entries so we can stop now */
             ixEthDBReleaseHashIterator(&iterator);

             IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");

             break;
         }
     }

     IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);

     return ixEthDBTreeRebalance(searchTree);
 }

 /**
  * @brief inserts a mac descriptor into an tree
  *
  * @param searchTree tree where the insertion is to be performed (may be NULL)
  * @param descriptor descriptor to insert into tree
  *
  * @return the tree root
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor)
 {
     MacTreeNode *currentNode    = searchTree;
     MacTreeNode *insertLocation = NULL;
     MacTreeNode *newNode;
     INT32 insertPosition = RIGHT;

     if (descriptor == NULL)
     {
         return searchTree;
     }

     /* create a new node */
     newNode = ixEthDBAllocMacTreeNode();

     if (newNode == NULL)
     {
         /* out of memory */
         ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);

         ixEthDBFreeMacDescriptor(descriptor);

         return NULL;
     }

     /* populate node */
     newNode->descriptor = descriptor;

     /* an empty initial tree is a special case */
     if (searchTree == NULL)
     {
         return newNode;
     }

     /* get insertion location */
     while (insertLocation == NULL)
     {
         MacTreeNode *nextNode;

         /* compare given key with current node key */
         insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);

         /* navigate down */
         if (insertPosition == RIGHT)
         {
             nextNode = currentNode->right;
         }
         else if (insertPosition == LEFT)
         {
             nextNode = currentNode->left;
         }
         else
         {
             /* error, duplicate key */
             ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");

             /* this will free the MAC descriptor as well */
             ixEthDBFreeMacTreeNode(newNode);

             return searchTree;
         }

         /* when we can no longer dive through the tree we found the insertion place */
         if (nextNode != NULL)
         {
             currentNode = nextNode;
         }
         else
         {
             insertLocation = currentNode;
         }
     }

     /* insert node */
     if (insertPosition == RIGHT)
     {
         insertLocation->right = newNode;
     }
     else
     {
         insertLocation->left = newNode;
     }

     return searchTree;
 }

 /**
  * @brief balance a tree
  *
  * @param searchTree tree to balance
  *
  * Converts a tree into a balanced tree and returns the root of
  * the balanced tree. The resulting tree is <i>route balanced</i>
  * not <i>perfectly balanced</i>. This makes no difference to the
  * average tree search time which is the same in both cases, O(log2(n)).
  *
  * @return root of the balanced tree or NULL if there's no memory left
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree)
 {
     MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();
     UINT32 size;

     if (pseudoRoot == NULL)
     {
         /* out of memory */
         return NULL;
     }

     pseudoRoot->right = searchTree;

     ixEthDBRebalanceTreeToVine(pseudoRoot, &size);
     ixEthDBRebalanceVineToTree(pseudoRoot, size);

     searchTree = pseudoRoot->right;

     /* remove pseudoRoot right branch, otherwise it will free the entire tree */
     pseudoRoot->right = NULL;

     ixEthDBFreeMacTreeNode(pseudoRoot);

     return searchTree;
 }

 /**
  * @brief converts a tree into a vine
  *
  * @param root root of tree to convert
  * @param size depth of vine (equal to the number of nodes in the tree)
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size)
 {
     MacTreeNode *vineTail  = root;
     MacTreeNode *remainder = vineTail->right;
     MacTreeNode *tempPtr;

     *size = 0;

     while (remainder != NULL)
     {
         if (remainder->left == NULL)
         {
             /* move tail down one */
             vineTail  = remainder;
             remainder = remainder->right;
             (*size)++;
         }
         else
         {
             /* rotate around remainder */
             tempPtr         = remainder->left;
             remainder->left = tempPtr->right;
             tempPtr->right  = remainder;
             remainder       = tempPtr;
             vineTail->right = tempPtr;
         }
     }
 }

 /**
  * @brief converts a vine into a balanced tree
  *
  * @param root vine to convert
  * @param size depth of vine
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size)
 {
     UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));

     ixEthDBRebalanceCompression(root, leafCount);

     size = size - leafCount;

     while (size > 1)
     {
         ixEthDBRebalanceCompression(root, size / 2);

         size /= 2;
     }
 }

 /**
  * @brief compresses a vine/tree stage into a more balanced vine/tree
  *
  * @param root root of the tree to compress
  * @param count number of "spine" nodes
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count)
 {
     MacTreeNode *scanner = root;
     MacTreeNode *child;
     UINT32 local_index;

     for (local_index = 0 ; local_index < count ; local_index++)
     {
         child          = scanner->right;
         scanner->right = child->right;
         scanner        = scanner->right;
         child->right   = scanner->left;
         scanner->left  = child;
     }
 }

 /**
  * @brief computes |_log2(x)_| (a.k.a. floor(log2(x)))
  *
  * @param x number to compute |_log2(x)_| for
  *
  * @return |_log2(x)_|
  *
  * @internal
  */
 IX_ETH_DB_PRIVATE
 UINT32 ixEthDBRebalanceLog2Floor(UINT32 x)
 {
     UINT32 log = 0;
     UINT32 val = 1;

     while (val < x)
     {
         log++;
         val <<= 1;
     }

     return val == x ? log : log - 1;
 }
	/**
	* @file IxEthDBDBPortUpdate.c
	*
	* @brief Implementation of dependency and port update handling
	*
	* @par
	* IXP400 SW Release version 2.0
	*
	* -- Copyright Notice --
	*
	* @par
	* Copyright 2001-2005, Intel Corporation.
	* All rights reserved.
	*
	* @par
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of the Intel Corporation nor the names of its contributors
	* may be used to endorse or promote products derived from this software
	* without specific prior written permission.
	*
	* @par
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	* SUCH DAMAGE.
	*
	* @par
	* -- End of Copyright Notice --
	*/

	#include "IxEthDB_p.h"

	/* forward prototype declarations */
	IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode searchTree, MacDescriptor descriptor);
	IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
	IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
	IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode root, UINT32 size);
	IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
	IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
	IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);

	extern HashTable dbHashtable;

	/**
	* @brief register types requiring automatic updates
	*
	* @param typeArray array indexed on record types, each
	* element indicating whether the record type requires an
	* automatic update (true) or not (false)
	*
	* Automatic updates are done for registered record types
	* upon adding, updating (that is, updating the record portID)
	* and removing records. Whenever an automatic update is triggered
	* the appropriate ports will be provided with new database
	* information.
	*
	* It is assumed that the typeArray parameter is allocated large
	* enough to hold all the user defined types. Also, the type
	* array should be initialized to false as this function only
	* caters for types which do require automatic updates.
	*
	* Note that this function should be called by the component
	* initialization function.
	*
	* @return number of record types registered for automatic
	* updates
	*
	* @internal
	*/
	IX_ETH_DB_PUBLIC
	UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
	{
	typeArray[IX_ETH_DB_FILTERING_RECORD] = true;
	typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true;

	return 2;
	}

	/**
	* @brief computes dependencies and triggers port learning tree updates
	*
	* @param triggerPorts port map consisting in the ports which triggered the update
	*
	* This function browses through all the ports and determines how to waterfall the update
	* event from the trigger ports to all other ports depending on them.
	*
	* Once the list of ports to be updated is determined this function
	* calls @ref ixEthDBCreateTrees.
	*
	* @internal
	*/
	IX_ETH_DB_PUBLIC
	void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts)
	{
	IxEthDBPortMap updatePorts;
	UINT32 portIndex;

	ixEthDBUpdateLock();

	SET_EMPTY_DEPENDENCY_MAP(updatePorts);

	for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
	{
	PortInfo *port = &ixEthDBPortInfo[portIndex];
	BOOL mapsCollide;

	MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap);

	if (mapsCollide /* do triggers influence this port? */
	&& !IS_PORT_INCLUDED(portIndex, updatePorts) /* and it's not already in the update list */
	&& port->updateMethod.updateEnabled) /* and we're allowed to update it */
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex);

	JOIN_PORT_TO_MAP(updatePorts, portIndex);
	}
	else
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex);

	if (!mapsCollide)
	{
	IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex);
	}

	if (IS_PORT_INCLUDED(portIndex, updatePorts))
	{
	IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex);
	}

	if (!port->updateMethod.updateEnabled)
	{
	IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex);
	}
	}
	}

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n");

	ixEthDBCreateTrees(updatePorts);

	ixEthDBUpdateUnlock();
	}

	/**
	* @brief creates learning trees and calls the port update handlers
	*
	* @param updatePorts set of ports in need of learning trees
	*
	* This function determines the optimal method of creating learning
	* trees using a minimal number of database queries, keeping in mind
	* that different ports can either use the same learning trees or they
	* can partially share them. The actual tree building routine is
	* @ref ixEthDBQuery.
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
	{
	UINT32 portIndex;
	BOOL result;
	BOOL portsLeft = true;

	while (portsLeft)
	{
	/* get port with minimal dependency map and NULL search tree */
	UINT32 minPortIndex = MAX_PORT_SIZE;
	UINT32 minimalSize = MAX_PORT_SIZE;

	for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
	{
	UINT32 size;
	PortInfo *port = &ixEthDBPortInfo[portIndex];

	/* generate trees only for ports that need them */
	if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts))
	{
	GET_MAP_SIZE(port->dependencyPortMap, size);

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n",
	portIndex, size);

	if (size < minimalSize)
	{
	minPortIndex = portIndex;
	minimalSize = size;
	}
	}
	else
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex,
	port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query");
	}
	}

	/* if a port was found than minimalSize is not MAX_PORT_SIZE */
	if (minimalSize != MAX_PORT_SIZE)
	{
	/* minPortIndex is the port we seek */
	PortInfo *port = &ixEthDBPortInfo[minPortIndex];

	IxEthDBPortMap query;
	MacTreeNode *baseTree;

	/* now try to find a port with minimal map difference */
	PortInfo *minimalDiffPort = NULL;
	UINT32 minimalDiff = MAX_PORT_SIZE;

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex);

	for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
	{
	PortInfo *diffPort = &ixEthDBPortInfo[portIndex];
	BOOL mapIsSubset;

	IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap);


	if (portIndex != minPortIndex
	&& diffPort->updateMethod.searchTree != NULL
	&& mapIsSubset)
	{
	/* compute size and pick only minimal size difference */
	UINT32 diffPortSize;
	UINT32 sizeDifference;

	GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize);

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex);

	sizeDifference = minimalSize - diffPortSize;

	if (sizeDifference < minimalDiff)
	{
	minimalDiffPort = diffPort;
	minimalDiff = sizeDifference;

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n",
	minimalDiff, portIndex);
	}
	}
	}

	/* check if filtering is enabled on this port */
	if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0)
	{
	/* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */
	if (minimalDiff != MAX_PORT_SIZE)
	{
	baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree);
	DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap);

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n",
	minimalDiffPort->portID);
	}
	else /* .. otherwise no similar port was found, build tree from scratch */
	{
	baseTree = NULL;

	COPY_DEPENDENCY_MAP(query, port->dependencyPortMap);

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n");
	}

	IS_EMPTY_DEPENDENCY_MAP(result, query);

	if (!result) /* otherwise we don't need anything more on top of the cloned tree */
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex);

	/* build learning tree */
	port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE);
	}
	else
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n");

	port->updateMethod.searchTree = baseTree;
	}
	}
	else
	{
	/* filtering is not enabled, will download an empty tree */
	if (port->updateMethod.searchTree != NULL)
	{
	ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
	}

	port->updateMethod.searchTree = NULL;
	}

	/* mark tree as valid */
	port->updateMethod.searchTreePendingWrite = true;
	}
	else
	{
	portsLeft = false;

	IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n");
	}
	}

	for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
	{
	PortInfo *updatePort = &ixEthDBPortInfo[portIndex];

	if (updatePort->updateMethod.searchTreePendingWrite)
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n",
	updatePort->updateMethod.searchTree != NULL ? "not " : "",
	portIndex);

	updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD);
	}
	}
	}

	/**
	* @brief standard NPE update handler
	*
	* @param portID id of the port to be updated
	* @param type record type to be pushed during this update
	*
	* The NPE update handler manages updating the NPE databases
	* given a certain record type.
	*
	* @internal
	*/
	IX_ETH_DB_PUBLIC
	IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type)
	{
	UINT32 epDelta, blockCount;
	IxNpeMhMessage message;
	UINT32 treeSize = 0;
	PortInfo *port = &ixEthDBPortInfo[portID];

	/* size selection and type check */
	if (type == IX_ETH_DB_FILTERING_RECORD \|\| type == IX_ETH_DB_WIFI_RECORD)
	{
	treeSize = FULL_ELT_BYTE_SIZE;
	}
	else if (type == IX_ETH_DB_FIREWALL_RECORD)
	{
	treeSize = FULL_FW_BYTE_SIZE;
	}
	else
	{
	return IX_ETH_DB_INVALID_ARG;
	}

	/* serialize tree into memory */
	ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount);

	/* free internal copy */
	if (port->updateMethod.searchTree != NULL)
	{
	ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
	}

	/* forget last used search tree */
	port->updateMethod.searchTree = NULL;
	port->updateMethod.searchTreePendingWrite = false;

	/* dependending on the update type we do different things */
	if (type == IX_ETH_DB_FILTERING_RECORD \|\| type == IX_ETH_DB_WIFI_RECORD)
	{
	IX_STATUS result;

	FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),
	epDelta, blockCount,
	IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));

	IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);

	if (result == IX_SUCCESS)
	{
	IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);
	}
	else
	{
	ixEthDBPortInfo[portID].agingEnabled = false;
	ixEthDBPortInfo[portID].updateMethod.updateEnabled = false;
	ixEthDBPortInfo[portID].updateMethod.userControlled = true;

	ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);

	ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);

	return IX_ETH_DB_FAIL;
	}

	return IX_ETH_DB_SUCCESS;
	}
	else if (type == IX_ETH_DB_FIREWALL_RECORD)
	{
	return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);
	}

	return IX_ETH_DB_INVALID_ARG;
	}

	/**
	* @brief queries the database for a set of records to be inserted into a given tree
	*
	* @param searchTree pointer to a tree where insertions will be performed; can be NULL
	* @param query set of ports that a database record must match to be inserted into the tree
	*
	* The query method browses through the database, extracts all the descriptors matching
	* the given query parameter and inserts them into the given learning tree.
	* Note that this is an append procedure, the given tree needs not to be empty.
	* A "descriptor matching the query" is a descriptor whose port id is in the query map.
	* If the given tree is empty (NULL) a new tree is created and returned.
	*
	* @return the tree root
	*
	* @internal
	*/
	IX_ETH_DB_PUBLIC
	MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries)
	{
	HashIterator iterator;
	UINT32 entryCount = 0;

	/* browse database */
	BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));

	while (IS_ITERATOR_VALID(&iterator))
	{
	MacDescriptor descriptor = (MacDescriptor ) iterator.node->data;

	IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",
	mac2string(descriptor->macAddress),
	descriptor->portID);

	if ((descriptor->type & recordFilter) != 0
	&& IS_PORT_INCLUDED(descriptor->portID, query))
	{
	MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);

	IX_ETH_DB_UPDATE_TRACE("match\n");

	if (descriptorClone != NULL)
	{
	/* add descriptor to tree */
	searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);

	entryCount++;
	}
	}
	else
	{
	IX_ETH_DB_UPDATE_TRACE("no match\n");
	}

	if (entryCount < maxEntries)
	{
	/* advance to the next record */
	BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));
	}
	else
	{
	/* the NPE won't accept more entries so we can stop now */
	ixEthDBReleaseHashIterator(&iterator);

	IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");

	break;
	}
	}

	IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);

	return ixEthDBTreeRebalance(searchTree);
	}

	/**
	* @brief inserts a mac descriptor into an tree
	*
	* @param searchTree tree where the insertion is to be performed (may be NULL)
	* @param descriptor descriptor to insert into tree
	*
	* @return the tree root
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	MacTreeNode* ixEthDBTreeInsert(MacTreeNode searchTree, MacDescriptor descriptor)
	{
	MacTreeNode *currentNode = searchTree;
	MacTreeNode *insertLocation = NULL;
	MacTreeNode *newNode;
	INT32 insertPosition = RIGHT;

	if (descriptor == NULL)
	{
	return searchTree;
	}

	/* create a new node */
	newNode = ixEthDBAllocMacTreeNode();

	if (newNode == NULL)
	{
	/* out of memory */
	ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);

	ixEthDBFreeMacDescriptor(descriptor);

	return NULL;
	}

	/* populate node */
	newNode->descriptor = descriptor;

	/* an empty initial tree is a special case */
	if (searchTree == NULL)
	{
	return newNode;
	}

	/* get insertion location */
	while (insertLocation == NULL)
	{
	MacTreeNode *nextNode;

	/* compare given key with current node key */
	insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);

	/* navigate down */
	if (insertPosition == RIGHT)
	{
	nextNode = currentNode->right;
	}
	else if (insertPosition == LEFT)
	{
	nextNode = currentNode->left;
	}
	else
	{
	/* error, duplicate key */
	ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");

	/* this will free the MAC descriptor as well */
	ixEthDBFreeMacTreeNode(newNode);

	return searchTree;
	}

	/* when we can no longer dive through the tree we found the insertion place */
	if (nextNode != NULL)
	{
	currentNode = nextNode;
	}
	else
	{
	insertLocation = currentNode;
	}
	}

	/* insert node */
	if (insertPosition == RIGHT)
	{
	insertLocation->right = newNode;
	}
	else
	{
	insertLocation->left = newNode;
	}

	return searchTree;
	}

	/**
	* @brief balance a tree
	*
	* @param searchTree tree to balance
	*
	* Converts a tree into a balanced tree and returns the root of
	* the balanced tree. The resulting tree is <i>route balanced</i>
	* not <i>perfectly balanced</i>. This makes no difference to the
	* average tree search time which is the same in both cases, O(log2(n)).
	*
	* @return root of the balanced tree or NULL if there's no memory left
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree)
	{
	MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();
	UINT32 size;

	if (pseudoRoot == NULL)
	{
	/* out of memory */
	return NULL;
	}

	pseudoRoot->right = searchTree;

	ixEthDBRebalanceTreeToVine(pseudoRoot, &size);
	ixEthDBRebalanceVineToTree(pseudoRoot, size);

	searchTree = pseudoRoot->right;

	/* remove pseudoRoot right branch, otherwise it will free the entire tree */
	pseudoRoot->right = NULL;

	ixEthDBFreeMacTreeNode(pseudoRoot);

	return searchTree;
	}

	/**
	* @brief converts a tree into a vine
	*
	* @param root root of tree to convert
	* @param size depth of vine (equal to the number of nodes in the tree)
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	void ixEthDBRebalanceTreeToVine(MacTreeNode root, UINT32 size)
	{
	MacTreeNode *vineTail = root;
	MacTreeNode *remainder = vineTail->right;
	MacTreeNode *tempPtr;

	*size = 0;

	while (remainder != NULL)
	{
	if (remainder->left == NULL)
	{
	/* move tail down one */
	vineTail = remainder;
	remainder = remainder->right;
	(*size)++;
	}
	else
	{
	/* rotate around remainder */
	tempPtr = remainder->left;
	remainder->left = tempPtr->right;
	tempPtr->right = remainder;
	remainder = tempPtr;
	vineTail->right = tempPtr;
	}
	}
	}

	/**
	* @brief converts a vine into a balanced tree
	*
	* @param root vine to convert
	* @param size depth of vine
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size)
	{
	UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));

	ixEthDBRebalanceCompression(root, leafCount);

	size = size - leafCount;

	while (size > 1)
	{
	ixEthDBRebalanceCompression(root, size / 2);

	size /= 2;
	}
	}

	/**
	* @brief compresses a vine/tree stage into a more balanced vine/tree
	*
	* @param root root of the tree to compress
	* @param count number of "spine" nodes
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count)
	{
	MacTreeNode *scanner = root;
	MacTreeNode *child;
	UINT32 local_index;

	for (local_index = 0 ; local_index < count ; local_index++)
	{
	child = scanner->right;
	scanner->right = child->right;
	scanner = scanner->right;
	child->right = scanner->left;
	scanner->left = child;
	}
	}

	/**
	* @brief computes \|_log2(x)_\| (a.k.a. floor(log2(x)))
	*
	* @param x number to compute \|_log2(x)_\| for
	*
	* @return \|_log2(x)_\|
	*
	* @internal
	*/
	IX_ETH_DB_PRIVATE
	UINT32 ixEthDBRebalanceLog2Floor(UINT32 x)
	{
	UINT32 log = 0;
	UINT32 val = 1;

	while (val < x)
	{
	log++;
	val <<= 1;
	}

	return val == x ? log : log - 1;
	}