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