/** * @file ethHash.c * * @brief Hashtable implementation * * @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" #include "IxEthDBLocks_p.h" /** * @addtogroup EthDB * * @{ */ /** * @brief initializes a hash table object * * @param hashTable uninitialized hash table structure * @param numBuckets number of buckets to use * @param entryHashFunction hash function used * to hash entire hash node data block (for adding) * @param matchFunctions array of match functions, indexed on type, * used to differentiate records with the same hash value * @param freeFunction function used to free node data blocks * * Initializes the given hash table object. * * @internal */ void ixEthDBInitHash(HashTable *hashTable, UINT32 numBuckets, HashFunction entryHashFunction, MatchFunction *matchFunctions, FreeFunction freeFunction) { UINT32 bucketIndex; UINT32 hashSize = numBuckets * sizeof(HashNode *); /* entry hashing, matching and freeing methods */ hashTable->entryHashFunction = entryHashFunction; hashTable->matchFunctions = matchFunctions; hashTable->freeFunction = freeFunction; /* buckets */ hashTable->numBuckets = numBuckets; /* set to 0 all buckets */ memset(hashTable->hashBuckets, 0, hashSize); /* init bucket locks - note that initially all mutexes are unlocked after MutexInit()*/ for (bucketIndex = 0 ; bucketIndex < numBuckets ; bucketIndex++) { ixOsalFastMutexInit(&hashTable->bucketLocks[bucketIndex]); } } /** * @brief adds an entry to the hash table * * @param hashTable hash table to add the entry to * @param entry entry to add * * The entry will be hashed using the entry hashing function and added to the * hash table, unless a locking blockage occurs, in which case the caller * should retry. * * @retval IX_ETH_DB_SUCCESS if adding <i>entry</i> has succeeded * @retval IX_ETH_DB_NOMEM if there's no memory left in the hash node pool * @retval IX_ETH_DB_BUSY if there's a locking failure on the insertion path * * @internal */ IX_ETH_DB_PUBLIC IxEthDBStatus ixEthDBAddHashEntry(HashTable *hashTable, void *entry) { UINT32 hashValue = hashTable->entryHashFunction(entry); UINT32 bucketIndex = hashValue % hashTable->numBuckets; HashNode *bucket = hashTable->hashBuckets[bucketIndex]; HashNode *newNode; LockStack locks; INIT_STACK(&locks); /* lock bucket */ PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]); /* lock insertion element (first in chain), if any */ if (bucket != NULL) { PUSH_LOCK(&locks, &bucket->lock); } /* get new node */ newNode = ixEthDBAllocHashNode(); if (newNode == NULL) { /* unlock everything */ UNROLL_STACK(&locks); return IX_ETH_DB_NOMEM; } /* init lock - note that mutexes are unlocked after MutexInit */ ixOsalFastMutexInit(&newNode->lock); /* populate new link */ newNode->data = entry; /* add to bucket */ newNode->next = bucket; hashTable->hashBuckets[bucketIndex] = newNode; /* unlock bucket and insertion point */ UNROLL_STACK(&locks); return IX_ETH_DB_SUCCESS; } /** * @brief removes an entry from the hashtable * * @param hashTable hash table to remove entry from * @param keyType type of record key used for matching * @param reference reference key used to identify the entry * * The reference key will be hashed using the key hashing function, * the entry is searched using the hashed value and then examined * against the reference entry using the match function. A positive * match will trigger the deletion of the entry. * Locking failures are reported and the caller should retry. * * @retval IX_ETH_DB_SUCCESS if the removal was successful * @retval IX_ETH_DB_NO_SUCH_ADDR if the entry was not found * @retval IX_ETH_DB_BUSY if a locking failure occured during the process * * @internal */ IxEthDBStatus ixEthDBRemoveHashEntry(HashTable *hashTable, int keyType, void *reference) { UINT32 hashValue = hashTable->entryHashFunction(reference); UINT32 bucketIndex = hashValue % hashTable->numBuckets; HashNode *node = hashTable->hashBuckets[bucketIndex]; HashNode *previousNode = NULL; LockStack locks; INIT_STACK(&locks); while (node != NULL) { /* try to lock node */ PUSH_LOCK(&locks, &node->lock); if (hashTable->matchFunctions[keyType](reference, node->data)) { /* found entry */ if (node->next != NULL) { PUSH_LOCK(&locks, &node->next->lock); } if (previousNode == NULL) { /* node is head of chain */ PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]); hashTable->hashBuckets[bucketIndex] = node->next; POP_LOCK(&locks); } else { /* relink */ previousNode->next = node->next; } UNROLL_STACK(&locks); /* free node */ hashTable->freeFunction(node->data); ixEthDBFreeHashNode(node); return IX_ETH_DB_SUCCESS; } else { if (previousNode != NULL) { /* unlock previous node */ SHIFT_STACK(&locks); } /* advance to next element in chain */ previousNode = node; node = node->next; } } UNROLL_STACK(&locks); /* not found */ return IX_ETH_DB_NO_SUCH_ADDR; } /** * @brief retrieves an entry from the hash table * * @param hashTable hash table to perform the search into * @param reference search key (a MAC address) * @param keyType type of record key used for matching * @param searchResult pointer where a reference to the located hash node * is placed * * Searches the entry with the same key as <i>reference</i> and places the * pointer to the resulting node in <i>searchResult</i>. * An implicit write access lock is granted after a search, which gives the * caller the opportunity to modify the entry. * Access should be released as soon as possible using @ref ixEthDBReleaseHashNode(). * * @see ixEthDBReleaseHashNode() * * @retval IX_ETH_DB_SUCCESS if the search was completed successfully * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case * the caller should retry * * @warning unless the return value is <b>IX_ETH_DB_SUCCESS</b> the searchResult * location is NOT modified and therefore using a NULL comparison test when the * value was not properly initialized would be an error * * @internal */ IxEthDBStatus ixEthDBSearchHashEntry(HashTable *hashTable, int keyType, void *reference, HashNode **searchResult) { UINT32 hashValue; HashNode *node; hashValue = hashTable->entryHashFunction(reference); node = hashTable->hashBuckets[hashValue % hashTable->numBuckets]; while (node != NULL) { TRY_LOCK(&node->lock); if (hashTable->matchFunctions[keyType](reference, node->data)) { *searchResult = node; return IX_ETH_DB_SUCCESS; } else { UNLOCK(&node->lock); node = node->next; } } /* not found */ return IX_ETH_DB_NO_SUCH_ADDR; } /** * @brief reports the existence of an entry in the hash table * * @param hashTable hash table to perform the search into * @param reference search key (a MAC address) * @param keyType type of record key used for matching * * Searches the entry with the same key as <i>reference</i>. * No implicit write access lock is granted after a search, hence the * caller cannot access or modify the entry. The result is only temporary. * * @see ixEthDBReleaseHashNode() * * @retval IX_ETH_DB_SUCCESS if the search was completed successfully * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case * the caller should retry * * @internal */ IxEthDBStatus ixEthDBPeekHashEntry(HashTable *hashTable, int keyType, void *reference) { UINT32 hashValue; HashNode *node; hashValue = hashTable->entryHashFunction(reference); node = hashTable->hashBuckets[hashValue % hashTable->numBuckets]; while (node != NULL) { TRY_LOCK(&node->lock); if (hashTable->matchFunctions[keyType](reference, node->data)) { UNLOCK(&node->lock); return IX_ETH_DB_SUCCESS; } else { UNLOCK(&node->lock); node = node->next; } } /* not found */ return IX_ETH_DB_NO_SUCH_ADDR; } /** * @brief releases the write access lock * * @pre the node should have been obtained via @ref ixEthDBSearchHashEntry() * * @see ixEthDBSearchHashEntry() * * @internal */ void ixEthDBReleaseHashNode(HashNode *node) { UNLOCK(&node->lock); } /** * @brief initializes a hash iterator * * @param hashTable hash table to be iterated * @param iterator iterator object * * If the initialization is successful the iterator will point to the * first hash table record (if any). * Testing if the iterator has not passed the end of the table should be * done using the IS_ITERATOR_VALID(iteratorPtr) macro. * An implicit write access lock is granted on the entry pointed by the iterator. * The access is automatically revoked when the iterator is incremented. * If the caller decides to terminate the iteration before the end of the table is * passed then the manual access release method, @ref ixEthDBReleaseHashIterator, * must be called. * * @see ixEthDBReleaseHashIterator() * * @retval IX_ETH_DB_SUCCESS if initialization was successful and the iterator points * to the first valid table node * @retval IX_ETH_DB_FAIL if the table is empty * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller * should retry * * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this * might place the database in a permanent invalid lock state * * @internal */ IxEthDBStatus ixEthDBInitHashIterator(HashTable *hashTable, HashIterator *iterator) { iterator->bucketIndex = 0; iterator->node = NULL; iterator->previousNode = NULL; return ixEthDBIncrementHashIterator(hashTable, iterator); } /** * @brief releases the write access locks of the iterator nodes * * @warning use of this function is required only when the caller terminates an iteration * before reaching the end of the table * * @see ixEthDBInitHashIterator() * @see ixEthDBIncrementHashIterator() * * @param iterator iterator whose node(s) should be unlocked * * @internal */ void ixEthDBReleaseHashIterator(HashIterator *iterator) { if (iterator->previousNode != NULL) { UNLOCK(&iterator->previousNode->lock); } if (iterator->node != NULL) { UNLOCK(&iterator->node->lock); } } /** * @brief incremenents an iterator so that it points to the next valid entry of the table * (if any) * * @param hashTable hash table to iterate * @param iterator iterator object * * @pre the iterator object must be initialized using @ref ixEthDBInitHashIterator() * * If the increment operation is successful the iterator will point to the * next hash table record (if any). * Testing if the iterator has not passed the end of the table should be * done using the IS_ITERATOR_VALID(iteratorPtr) macro. * An implicit write access lock is granted on the entry pointed by the iterator. * The access is automatically revoked when the iterator is re-incremented. * If the caller decides to terminate the iteration before the end of the table is * passed then the manual access release method, @ref ixEthDBReleaseHashIterator, * must be called. * Is is guaranteed that no other thread can remove or change the iterated entry until * the iterator is incremented successfully. * * @see ixEthDBReleaseHashIterator() * * @retval IX_ETH_DB_SUCCESS if the operation was successful and the iterator points * to the next valid table node * @retval IX_ETH_DB_FAIL if the iterator has passed the end of the table * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller * should retry * * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this * might place the database in a permanent invalid lock state * * @internal */ IxEthDBStatus ixEthDBIncrementHashIterator(HashTable *hashTable, HashIterator *iterator) { /* unless iterator is just initialized... */ if (iterator->node != NULL) { /* try next in chain */ if (iterator->node->next != NULL) { TRY_LOCK(&iterator->node->next->lock); if (iterator->previousNode != NULL) { UNLOCK(&iterator->previousNode->lock); } iterator->previousNode = iterator->node; iterator->node = iterator->node->next; return IX_ETH_DB_SUCCESS; } else { /* last in chain, prepare for next bucket */ iterator->bucketIndex++; } } /* try next used bucket */ for (; iterator->bucketIndex < hashTable->numBuckets ; iterator->bucketIndex++) { HashNode **nodePtr = &(hashTable->hashBuckets[iterator->bucketIndex]); HashNode *node = *nodePtr; #if (CPU!=SIMSPARCSOLARIS) && !defined (__wince) if (((iterator->bucketIndex & IX_ETHDB_BUCKET_INDEX_MASK) == 0) && (iterator->bucketIndex < (hashTable->numBuckets - IX_ETHDB_BUCKETPTR_AHEAD))) { /* preload next cache line (2 cache line ahead) */ nodePtr += IX_ETHDB_BUCKETPTR_AHEAD; __asm__ ("pld [%0];\n": : "r" (nodePtr)); } #endif if (node != NULL) { TRY_LOCK(&node->lock); /* unlock last one or two nodes in the previous chain */ if (iterator->node != NULL) { UNLOCK(&iterator->node->lock); if (iterator->previousNode != NULL) { UNLOCK(&iterator->previousNode->lock); } } /* redirect iterator */ iterator->previousNode = NULL; iterator->node = node; return IX_ETH_DB_SUCCESS; } } /* could not advance iterator */ if (iterator->node != NULL) { UNLOCK(&iterator->node->lock); if (iterator->previousNode != NULL) { UNLOCK(&iterator->previousNode->lock); } iterator->node = NULL; } return IX_ETH_DB_END; } /** * @brief removes an entry pointed by an iterator * * @param hashTable iterated hash table * @param iterator iterator object * * Removes the entry currently pointed by the iterator and repositions the iterator * on the next valid entry (if any). Handles locking issues automatically and * implicitely grants write access lock to the new pointed entry. * Failures due to concurrent threads having write access locks in the same region * preserve the state of the database and the iterator object, leaving the caller * free to retry without loss of access. It is guaranteed that only the thread owning * the iterator can remove the object pointed by the iterator. * * @retval IX_ETH_DB_SUCCESS if removal has succeeded * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller * should retry * * @internal */ IxEthDBStatus ixEthDBRemoveEntryAtHashIterator(HashTable *hashTable, HashIterator *iterator) { HashIterator nextIteratorPos; LockStack locks; INIT_STACK(&locks); /* set initial bucket index for next position */ nextIteratorPos.bucketIndex = iterator->bucketIndex; /* compute iterator position before removing anything and lock ahead */ if (iterator->node->next != NULL) { PUSH_LOCK(&locks, &iterator->node->next->lock); /* reposition on the next node in the chain */ nextIteratorPos.node = iterator->node->next; nextIteratorPos.previousNode = iterator->previousNode; } else { /* try next chain - don't know yet if we'll find anything */ nextIteratorPos.node = NULL; /* if we find something it's a chain head */ nextIteratorPos.previousNode = NULL; /* browse up in the buckets to find a non-null chain */ while (++nextIteratorPos.bucketIndex < hashTable->numBuckets) { nextIteratorPos.node = hashTable->hashBuckets[nextIteratorPos.bucketIndex]; if (nextIteratorPos.node != NULL) { /* found a non-empty chain, try to lock head */ PUSH_LOCK(&locks, &nextIteratorPos.node->lock); break; } } } /* restore links over the to-be-deleted item */ if (iterator->previousNode == NULL) { /* first in chain, lock bucket */ PUSH_LOCK(&locks, &hashTable->bucketLocks[iterator->bucketIndex]); hashTable->hashBuckets[iterator->bucketIndex] = iterator->node->next; POP_LOCK(&locks); } else { /* relink */ iterator->previousNode->next = iterator->node->next; /* unlock last remaining node in current chain when moving between chains */ if (iterator->node->next == NULL) { UNLOCK(&iterator->previousNode->lock); } } /* delete entry */ hashTable->freeFunction(iterator->node->data); ixEthDBFreeHashNode(iterator->node); /* reposition iterator */ *iterator = nextIteratorPos; return IX_ETH_DB_SUCCESS; } /** * @} */