/** * @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_PUBLICUINT32 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_PUBLICvoid 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_PRIVATEvoid 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_PUBLICIxEthDBStatus 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)    {