diff options
Diffstat (limited to 'cpu/ixp/npe/IxEthDBPortUpdate.c')
| -rw-r--r-- | cpu/ixp/npe/IxEthDBPortUpdate.c | 740 |
1 files changed, 740 insertions, 0 deletions
diff --git a/cpu/ixp/npe/IxEthDBPortUpdate.c b/cpu/ixp/npe/IxEthDBPortUpdate.c new file mode 100644 index 0000000000..cdf114bfc4 --- /dev/null +++ b/cpu/ixp/npe/IxEthDBPortUpdate.c @@ -0,0 +1,740 @@ +/** + * @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; +} + |