2 * @file IxEthDBDBPortUpdate.c
4 * @brief Implementation of dependency and port update handling
7 * IXP400 SW Release version 2.0
9 * -- Copyright Notice --
12 * Copyright 2001-2005, Intel Corporation.
13 * All rights reserved.
16 * SPDX-License-Identifier: BSD-3-Clause
18 * -- End of Copyright Notice --
21 #include "IxEthDB_p.h"
23 /* forward prototype declarations */
24 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor);
25 IX_ETH_DB_PRIVATE void ixEthDBCreateTrees(IxEthDBPortMap updatePorts);
26 IX_ETH_DB_PRIVATE MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree);
27 IX_ETH_DB_PRIVATE void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size);
28 IX_ETH_DB_PRIVATE void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size);
29 IX_ETH_DB_PRIVATE void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count);
30 IX_ETH_DB_PRIVATE UINT32 ixEthDBRebalanceLog2Floor(UINT32 x);
32 extern HashTable dbHashtable;
35 * @brief register types requiring automatic updates
37 * @param typeArray array indexed on record types, each
38 * element indicating whether the record type requires an
39 * automatic update (true) or not (false)
41 * Automatic updates are done for registered record types
42 * upon adding, updating (that is, updating the record portID)
43 * and removing records. Whenever an automatic update is triggered
44 * the appropriate ports will be provided with new database
47 * It is assumed that the typeArray parameter is allocated large
48 * enough to hold all the user defined types. Also, the type
49 * array should be initialized to false as this function only
50 * caters for types which do require automatic updates.
52 * Note that this function should be called by the component
53 * initialization function.
55 * @return number of record types registered for automatic
61 UINT32 ixEthDBUpdateTypeRegister(BOOL *typeArray)
63 typeArray[IX_ETH_DB_FILTERING_RECORD] = true;
64 typeArray[IX_ETH_DB_FILTERING_VLAN_RECORD] = true;
70 * @brief computes dependencies and triggers port learning tree updates
72 * @param triggerPorts port map consisting in the ports which triggered the update
74 * This function browses through all the ports and determines how to waterfall the update
75 * event from the trigger ports to all other ports depending on them.
77 * Once the list of ports to be updated is determined this function
78 * calls @ref ixEthDBCreateTrees.
83 void ixEthDBUpdatePortLearningTrees(IxEthDBPortMap triggerPorts)
85 IxEthDBPortMap updatePorts;
90 SET_EMPTY_DEPENDENCY_MAP(updatePorts);
92 for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
94 PortInfo *port = &ixEthDBPortInfo[portIndex];
97 MAPS_COLLIDE(mapsCollide, triggerPorts, port->dependencyPortMap);
99 if (mapsCollide /* do triggers influence this port? */
100 && !IS_PORT_INCLUDED(portIndex, updatePorts) /* and it's not already in the update list */
101 && port->updateMethod.updateEnabled) /* and we're allowed to update it */
103 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding port %d to update set\n", portIndex);
105 JOIN_PORT_TO_MAP(updatePorts, portIndex);
109 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Didn't add port %d to update set, reasons follow:\n", portIndex);
113 IX_ETH_DB_UPDATE_TRACE("\tMaps don't collide on port %d\n", portIndex);
116 if (IS_PORT_INCLUDED(portIndex, updatePorts))
118 IX_ETH_DB_UPDATE_TRACE("\tPort %d is already in the update set\n", portIndex);
121 if (!port->updateMethod.updateEnabled)
123 IX_ETH_DB_UPDATE_TRACE("\tPort %d doesn't have updateEnabled set\n", portIndex);
128 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Updating port set\n");
130 ixEthDBCreateTrees(updatePorts);
132 ixEthDBUpdateUnlock();
136 * @brief creates learning trees and calls the port update handlers
138 * @param updatePorts set of ports in need of learning trees
140 * This function determines the optimal method of creating learning
141 * trees using a minimal number of database queries, keeping in mind
142 * that different ports can either use the same learning trees or they
143 * can partially share them. The actual tree building routine is
149 void ixEthDBCreateTrees(IxEthDBPortMap updatePorts)
153 BOOL portsLeft = true;
157 /* get port with minimal dependency map and NULL search tree */
158 UINT32 minPortIndex = MAX_PORT_SIZE;
159 UINT32 minimalSize = MAX_PORT_SIZE;
161 for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
164 PortInfo *port = &ixEthDBPortInfo[portIndex];
166 /* generate trees only for ports that need them */
167 if (!port->updateMethod.searchTreePendingWrite && IS_PORT_INCLUDED(portIndex, updatePorts))
169 GET_MAP_SIZE(port->dependencyPortMap, size);
171 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Dependency map for port %d: size %d\n",
174 if (size < minimalSize)
176 minPortIndex = portIndex;
182 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Skipped port %d from tree diff (%s)\n", portIndex,
183 port->updateMethod.searchTreePendingWrite ? "pending write access" : "ignored by query");
187 /* if a port was found than minimalSize is not MAX_PORT_SIZE */
188 if (minimalSize != MAX_PORT_SIZE)
190 /* minPortIndex is the port we seek */
191 PortInfo *port = &ixEthDBPortInfo[minPortIndex];
193 IxEthDBPortMap query;
194 MacTreeNode *baseTree;
196 /* now try to find a port with minimal map difference */
197 PortInfo *minimalDiffPort = NULL;
198 UINT32 minimalDiff = MAX_PORT_SIZE;
200 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal size port is %d\n", minPortIndex);
202 for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
204 PortInfo *diffPort = &ixEthDBPortInfo[portIndex];
207 IS_MAP_SUBSET(mapIsSubset, diffPort->dependencyPortMap, port->dependencyPortMap);
210 if (portIndex != minPortIndex
211 && diffPort->updateMethod.searchTree != NULL
214 /* compute size and pick only minimal size difference */
216 UINT32 sizeDifference;
218 GET_MAP_SIZE(diffPort->dependencyPortMap, diffPortSize);
220 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Checking port %d for differences...\n", portIndex);
222 sizeDifference = minimalSize - diffPortSize;
224 if (sizeDifference < minimalDiff)
226 minimalDiffPort = diffPort;
227 minimalDiff = sizeDifference;
229 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Minimal difference 0x%x was found on port %d\n",
230 minimalDiff, portIndex);
235 /* check if filtering is enabled on this port */
236 if ((port->featureStatus & IX_ETH_DB_FILTERING) != 0)
238 /* if minimalDiff is not MAX_PORT_SIZE minimalDiffPort points to the most similar port */
239 if (minimalDiff != MAX_PORT_SIZE)
241 baseTree = ixEthDBCloneMacTreeNode(minimalDiffPort->updateMethod.searchTree);
242 DIFF_MAPS(query, port->dependencyPortMap , minimalDiffPort->dependencyPortMap);
244 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Found minimal diff, extending tree %d on query\n",
245 minimalDiffPort->portID);
247 else /* .. otherwise no similar port was found, build tree from scratch */
251 COPY_DEPENDENCY_MAP(query, port->dependencyPortMap);
253 IX_ETH_DB_UPDATE_TRACE("DB: (Update) No similar diff, creating tree from query\n");
256 IS_EMPTY_DEPENDENCY_MAP(result, query);
258 if (!result) /* otherwise we don't need anything more on top of the cloned tree */
260 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Adding query tree to port %d\n", minPortIndex);
262 /* build learning tree */
263 port->updateMethod.searchTree = ixEthDBQuery(baseTree, query, IX_ETH_DB_ALL_FILTERING_RECORDS, MAX_ELT_SIZE);
267 IX_ETH_DB_UPDATE_TRACE("DB: (Update) Query is empty, assuming identical nearest tree\n");
269 port->updateMethod.searchTree = baseTree;
274 /* filtering is not enabled, will download an empty tree */
275 if (port->updateMethod.searchTree != NULL)
277 ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
280 port->updateMethod.searchTree = NULL;
283 /* mark tree as valid */
284 port->updateMethod.searchTreePendingWrite = true;
290 IX_ETH_DB_UPDATE_TRACE("DB: (Update) No trees to create this round\n");
294 for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
296 PortInfo *updatePort = &ixEthDBPortInfo[portIndex];
298 if (updatePort->updateMethod.searchTreePendingWrite)
300 IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Starting procedure to upload new search tree (%snull) into NPE %d\n",
301 updatePort->updateMethod.searchTree != NULL ? "not " : "",
304 updatePort->updateMethod.updateHandler(portIndex, IX_ETH_DB_FILTERING_RECORD);
310 * @brief standard NPE update handler
312 * @param portID id of the port to be updated
313 * @param type record type to be pushed during this update
315 * The NPE update handler manages updating the NPE databases
316 * given a certain record type.
321 IxEthDBStatus ixEthDBNPEUpdateHandler(IxEthDBPortId portID, IxEthDBRecordType type)
323 UINT32 epDelta, blockCount;
324 IxNpeMhMessage message;
326 PortInfo *port = &ixEthDBPortInfo[portID];
328 /* size selection and type check */
329 if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
331 treeSize = FULL_ELT_BYTE_SIZE;
333 else if (type == IX_ETH_DB_FIREWALL_RECORD)
335 treeSize = FULL_FW_BYTE_SIZE;
339 return IX_ETH_DB_INVALID_ARG;
342 /* serialize tree into memory */
343 ixEthDBNPETreeWrite(type, treeSize, port->updateMethod.npeUpdateZone, port->updateMethod.searchTree, &epDelta, &blockCount);
345 /* free internal copy */
346 if (port->updateMethod.searchTree != NULL)
348 ixEthDBFreeMacTreeNode(port->updateMethod.searchTree);
351 /* forget last used search tree */
352 port->updateMethod.searchTree = NULL;
353 port->updateMethod.searchTreePendingWrite = false;
355 /* dependending on the update type we do different things */
356 if (type == IX_ETH_DB_FILTERING_RECORD || type == IX_ETH_DB_WIFI_RECORD)
360 FILL_SETMACADDRESSDATABASE_MSG(message, IX_ETH_DB_PORT_ID_TO_NPE_LOGICAL_ID(portID),
362 IX_OSAL_MMU_VIRT_TO_PHYS(port->updateMethod.npeUpdateZone));
364 IX_ETHDB_SEND_NPE_MSG(IX_ETH_DB_PORT_ID_TO_NPE(portID), message, result);
366 if (result == IX_SUCCESS)
368 IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) Finished downloading NPE tree on port %d\n", portID);
372 ixEthDBPortInfo[portID].agingEnabled = false;
373 ixEthDBPortInfo[portID].updateMethod.updateEnabled = false;
374 ixEthDBPortInfo[portID].updateMethod.userControlled = true;
376 ERROR_LOG("EthDB: (PortUpdate) disabling aging and updates on port %d (assumed dead)\n", portID);
378 ixEthDBDatabaseClear(portID, IX_ETH_DB_ALL_RECORD_TYPES);
380 return IX_ETH_DB_FAIL;
383 return IX_ETH_DB_SUCCESS;
385 else if (type == IX_ETH_DB_FIREWALL_RECORD)
387 return ixEthDBFirewallUpdate(portID, port->updateMethod.npeUpdateZone, epDelta);
390 return IX_ETH_DB_INVALID_ARG;
394 * @brief queries the database for a set of records to be inserted into a given tree
396 * @param searchTree pointer to a tree where insertions will be performed; can be NULL
397 * @param query set of ports that a database record must match to be inserted into the tree
399 * The query method browses through the database, extracts all the descriptors matching
400 * the given query parameter and inserts them into the given learning tree.
401 * Note that this is an append procedure, the given tree needs not to be empty.
402 * A "descriptor matching the query" is a descriptor whose port id is in the query map.
403 * If the given tree is empty (NULL) a new tree is created and returned.
405 * @return the tree root
410 MacTreeNode* ixEthDBQuery(MacTreeNode *searchTree, IxEthDBPortMap query, IxEthDBRecordType recordFilter, UINT32 maxEntries)
412 HashIterator iterator;
413 UINT32 entryCount = 0;
415 /* browse database */
416 BUSY_RETRY(ixEthDBInitHashIterator(&dbHashtable, &iterator));
418 while (IS_ITERATOR_VALID(&iterator))
420 MacDescriptor *descriptor = (MacDescriptor *) iterator.node->data;
422 IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) querying [%s]:%d on port map ... ",
423 mac2string(descriptor->macAddress),
426 if ((descriptor->type & recordFilter) != 0
427 && IS_PORT_INCLUDED(descriptor->portID, query))
429 MacDescriptor *descriptorClone = ixEthDBCloneMacDescriptor(descriptor);
431 IX_ETH_DB_UPDATE_TRACE("match\n");
433 if (descriptorClone != NULL)
435 /* add descriptor to tree */
436 searchTree = ixEthDBTreeInsert(searchTree, descriptorClone);
443 IX_ETH_DB_UPDATE_TRACE("no match\n");
446 if (entryCount < maxEntries)
448 /* advance to the next record */
449 BUSY_RETRY(ixEthDBIncrementHashIterator(&dbHashtable, &iterator));
453 /* the NPE won't accept more entries so we can stop now */
454 ixEthDBReleaseHashIterator(&iterator);
456 IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) number of elements reached maximum supported by port\n");
462 IX_ETH_DB_UPDATE_TRACE("DB: (PortUpdate) query inserted %d records in the search tree\n", entryCount);
464 return ixEthDBTreeRebalance(searchTree);
468 * @brief inserts a mac descriptor into an tree
470 * @param searchTree tree where the insertion is to be performed (may be NULL)
471 * @param descriptor descriptor to insert into tree
473 * @return the tree root
478 MacTreeNode* ixEthDBTreeInsert(MacTreeNode *searchTree, MacDescriptor *descriptor)
480 MacTreeNode *currentNode = searchTree;
481 MacTreeNode *insertLocation = NULL;
482 MacTreeNode *newNode;
483 INT32 insertPosition = RIGHT;
485 if (descriptor == NULL)
490 /* create a new node */
491 newNode = ixEthDBAllocMacTreeNode();
496 ERROR_LOG("Warning: ixEthDBAllocMacTreeNode returned NULL in file %s:%d (out of memory?)\n", __FILE__, __LINE__);
498 ixEthDBFreeMacDescriptor(descriptor);
504 newNode->descriptor = descriptor;
506 /* an empty initial tree is a special case */
507 if (searchTree == NULL)
512 /* get insertion location */
513 while (insertLocation == NULL)
515 MacTreeNode *nextNode;
517 /* compare given key with current node key */
518 insertPosition = ixEthDBAddressCompare(descriptor->macAddress, currentNode->descriptor->macAddress);
521 if (insertPosition == RIGHT)
523 nextNode = currentNode->right;
525 else if (insertPosition == LEFT)
527 nextNode = currentNode->left;
531 /* error, duplicate key */
532 ERROR_LOG("Warning: trapped insertion of a duplicate MAC address in an NPE search tree\n");
534 /* this will free the MAC descriptor as well */
535 ixEthDBFreeMacTreeNode(newNode);
540 /* when we can no longer dive through the tree we found the insertion place */
541 if (nextNode != NULL)
543 currentNode = nextNode;
547 insertLocation = currentNode;
552 if (insertPosition == RIGHT)
554 insertLocation->right = newNode;
558 insertLocation->left = newNode;
565 * @brief balance a tree
567 * @param searchTree tree to balance
569 * Converts a tree into a balanced tree and returns the root of
570 * the balanced tree. The resulting tree is <i>route balanced</i>
571 * not <i>perfectly balanced</i>. This makes no difference to the
572 * average tree search time which is the same in both cases, O(log2(n)).
574 * @return root of the balanced tree or NULL if there's no memory left
579 MacTreeNode* ixEthDBTreeRebalance(MacTreeNode *searchTree)
581 MacTreeNode *pseudoRoot = ixEthDBAllocMacTreeNode();
584 if (pseudoRoot == NULL)
590 pseudoRoot->right = searchTree;
592 ixEthDBRebalanceTreeToVine(pseudoRoot, &size);
593 ixEthDBRebalanceVineToTree(pseudoRoot, size);
595 searchTree = pseudoRoot->right;
597 /* remove pseudoRoot right branch, otherwise it will free the entire tree */
598 pseudoRoot->right = NULL;
600 ixEthDBFreeMacTreeNode(pseudoRoot);
606 * @brief converts a tree into a vine
608 * @param root root of tree to convert
609 * @param size depth of vine (equal to the number of nodes in the tree)
614 void ixEthDBRebalanceTreeToVine(MacTreeNode *root, UINT32 *size)
616 MacTreeNode *vineTail = root;
617 MacTreeNode *remainder = vineTail->right;
618 MacTreeNode *tempPtr;
622 while (remainder != NULL)
624 if (remainder->left == NULL)
626 /* move tail down one */
627 vineTail = remainder;
628 remainder = remainder->right;
633 /* rotate around remainder */
634 tempPtr = remainder->left;
635 remainder->left = tempPtr->right;
636 tempPtr->right = remainder;
638 vineTail->right = tempPtr;
644 * @brief converts a vine into a balanced tree
646 * @param root vine to convert
647 * @param size depth of vine
652 void ixEthDBRebalanceVineToTree(MacTreeNode *root, UINT32 size)
654 UINT32 leafCount = size + 1 - (1 << ixEthDBRebalanceLog2Floor(size + 1));
656 ixEthDBRebalanceCompression(root, leafCount);
658 size = size - leafCount;
662 ixEthDBRebalanceCompression(root, size / 2);
669 * @brief compresses a vine/tree stage into a more balanced vine/tree
671 * @param root root of the tree to compress
672 * @param count number of "spine" nodes
677 void ixEthDBRebalanceCompression(MacTreeNode *root, UINT32 count)
679 MacTreeNode *scanner = root;
683 for (local_index = 0 ; local_index < count ; local_index++)
685 child = scanner->right;
686 scanner->right = child->right;
687 scanner = scanner->right;
688 child->right = scanner->left;
689 scanner->left = child;
694 * @brief computes |_log2(x)_| (a.k.a. floor(log2(x)))
696 * @param x number to compute |_log2(x)_| for
698 * @return |_log2(x)_|
703 UINT32 ixEthDBRebalanceLog2Floor(UINT32 x)
714 return val == x ? log : log - 1;