summaryrefslogtreecommitdiffstats
path: root/drivers/net/npe/IxEthDBPortUpdate.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/net/npe/IxEthDBPortUpdate.c')
-rw-r--r--drivers/net/npe/IxEthDBPortUpdate.c716
1 files changed, 0 insertions, 716 deletions
diff --git a/drivers/net/npe/IxEthDBPortUpdate.c b/drivers/net/npe/IxEthDBPortUpdate.c
deleted file mode 100644
index 92af331a54..0000000000
--- a/drivers/net/npe/IxEthDBPortUpdate.c
+++ /dev/null
@@ -1,716 +0,0 @@
-/**
- * @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
- * SPDX-License-Identifier: BSD-3-Clause
- * @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;
-}
-
OpenPOWER on IntegriCloud