cpu/ixp/npe/IxEthDBHashtable.c

   1 /**
   2  * @file ethHash.c
   3  *
   4  * @brief Hashtable implementation
   5  *
   6  * @par
   7  * IXP400 SW Release version 2.0
   8  *
   9  * -- Copyright Notice --
  10  *
  11  * @par
  12  * Copyright 2001-2005, Intel Corporation.
  13  * All rights reserved.
  14  *
  15  * @par
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions
  18  * are met:
  19  * 1. Redistributions of source code must retain the above copyright
  20  *    notice, this list of conditions and the following disclaimer.
  21  * 2. Redistributions in binary form must reproduce the above copyright
  22  *    notice, this list of conditions and the following disclaimer in the
  23  *    documentation and/or other materials provided with the distribution.
  24  * 3. Neither the name of the Intel Corporation nor the names of its contributors
  25  *    may be used to endorse or promote products derived from this software
  26  *    without specific prior written permission.
  27  *
  28  * @par
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
  30  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
  33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  *
  41  * @par
  42  * -- End of Copyright Notice --
  43  */
  44
  45
  46 #include "IxEthDB_p.h"
  47 #include "IxEthDBLocks_p.h"
  48
  49 /**
  50  * @addtogroup EthDB
  51  *
  52  * @{
  53  */
  54
  55 /**
  56  * @brief initializes a hash table object
  57  *
  58  * @param hashTable uninitialized hash table structure
  59  * @param numBuckets number of buckets to use
  60  * @param entryHashFunction hash function used
  61  * to hash entire hash node data block (for adding)
  62  * @param matchFunctions array of match functions, indexed on type,
  63  * used to differentiate records with the same hash value
  64  * @param freeFunction function used to free node data blocks
  65  *
  66  * Initializes the given hash table object.
  67  *
  68  * @internal
  69  */
  70 void ixEthDBInitHash(HashTable *hashTable,
  71                      UINT32 numBuckets,
  72                      HashFunction entryHashFunction,
  73                      MatchFunction *matchFunctions,
  74                      FreeFunction freeFunction)
  75 {
  76     UINT32 bucketIndex;
  77     UINT32 hashSize = numBuckets * sizeof(HashNode *);
  78
  79     /* entry hashing, matching and freeing methods */
  80     hashTable->entryHashFunction  = entryHashFunction;
  81     hashTable->matchFunctions     = matchFunctions;
  82     hashTable->freeFunction       = freeFunction;
  83
  84     /* buckets */
  85     hashTable->numBuckets = numBuckets;
  86
  87     /* set to 0 all buckets */
  88     memset(hashTable->hashBuckets, 0, hashSize);
  89
  90     /* init bucket locks - note that initially all mutexes are unlocked after MutexInit()*/
  91     for (bucketIndex = 0 ; bucketIndex < numBuckets ; bucketIndex++)
  92     {
  93         ixOsalFastMutexInit(&hashTable->bucketLocks[bucketIndex]);
  94     }
  95 }
  96
  97 /**
  98  * @brief adds an entry to the hash table
  99  *
 100  * @param hashTable hash table to add the entry to
 101  * @param entry entry to add
 102  *
 103  * The entry will be hashed using the entry hashing function and added to the
 104  * hash table, unless a locking blockage occurs, in which case the caller
 105  * should retry.
 106  *
 107  * @retval IX_ETH_DB_SUCCESS if adding <i>entry</i> has succeeded
 108  * @retval IX_ETH_DB_NOMEM if there's no memory left in the hash node pool
 109  * @retval IX_ETH_DB_BUSY if there's a locking failure on the insertion path
 110  *
 111  * @internal
 112  */
 113 IX_ETH_DB_PUBLIC IxEthDBStatus ixEthDBAddHashEntry(HashTable *hashTable, void *entry)
 114 {
 115     UINT32 hashValue   = hashTable->entryHashFunction(entry);
 116     UINT32 bucketIndex = hashValue % hashTable->numBuckets;
 117     HashNode *bucket   = hashTable->hashBuckets[bucketIndex];
 118     HashNode *newNode;
 119
 120     LockStack locks;
 121
 122     INIT_STACK(&locks);
 123
 124     /* lock bucket */
 125     PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);
 126
 127     /* lock insertion element (first in chain), if any */
 128     if (bucket != NULL)
 129     {
 130         PUSH_LOCK(&locks, &bucket->lock);
 131     }
 132
 133     /* get new node */
 134     newNode = ixEthDBAllocHashNode();
 135
 136     if (newNode == NULL)
 137     {
 138         /* unlock everything */
 139         UNROLL_STACK(&locks);
 140
 141         return IX_ETH_DB_NOMEM;
 142     }
 143
 144     /* init lock - note that mutexes are unlocked after MutexInit */
 145     ixOsalFastMutexInit(&newNode->lock);
 146
 147     /* populate new link */
 148     newNode->data = entry;
 149
 150     /* add to bucket */
 151     newNode->next                       = bucket;
 152     hashTable->hashBuckets[bucketIndex] = newNode;
 153
 154     /* unlock bucket and insertion point */
 155     UNROLL_STACK(&locks);
 156
 157     return IX_ETH_DB_SUCCESS;
 158 }
 159
 160 /**
 161  * @brief removes an entry from the hashtable
 162  *
 163  * @param hashTable hash table to remove entry from
 164  * @param keyType type of record key used for matching
 165  * @param reference reference key used to identify the entry
 166  *
 167  * The reference key will be hashed using the key hashing function,
 168  * the entry is searched using the hashed value and then examined
 169  * against the reference entry using the match function. A positive
 170  * match will trigger the deletion of the entry.
 171  * Locking failures are reported and the caller should retry.
 172  *
 173  * @retval IX_ETH_DB_SUCCESS if the removal was successful
 174  * @retval IX_ETH_DB_NO_SUCH_ADDR if the entry was not found
 175  * @retval IX_ETH_DB_BUSY if a locking failure occured during the process
 176  *
 177  * @internal
 178  */
 179 IxEthDBStatus ixEthDBRemoveHashEntry(HashTable *hashTable, int keyType, void *reference)
 180 {
 181     UINT32 hashValue       = hashTable->entryHashFunction(reference);
 182     UINT32 bucketIndex     = hashValue % hashTable->numBuckets;
 183     HashNode *node         = hashTable->hashBuckets[bucketIndex];
 184     HashNode *previousNode = NULL;
 185
 186     LockStack locks;
 187
 188     INIT_STACK(&locks);
 189
 190     while (node != NULL)
 191     {
 192         /* try to lock node */
 193         PUSH_LOCK(&locks, &node->lock);
 194
 195         if (hashTable->matchFunctions[keyType](reference, node->data))
 196         {
 197             /* found entry */
 198             if (node->next != NULL)
 199             {
 200                 PUSH_LOCK(&locks, &node->next->lock);
 201             }
 202
 203             if (previousNode == NULL)
 204             {
 205                 /* node is head of chain */
 206                 PUSH_LOCK(&locks, &hashTable->bucketLocks[bucketIndex]);
 207
 208                 hashTable->hashBuckets[bucketIndex] = node->next;
 209
 210                 POP_LOCK(&locks);
 211             }
 212             else
 213             {
 214                 /* relink */
 215                 previousNode->next = node->next;
 216             }
 217
 218             UNROLL_STACK(&locks);
 219
 220             /* free node */
 221             hashTable->freeFunction(node->data);
 222             ixEthDBFreeHashNode(node);
 223
 224             return IX_ETH_DB_SUCCESS;
 225         }
 226         else
 227         {
 228             if (previousNode != NULL)
 229             {
 230                 /* unlock previous node */
 231                 SHIFT_STACK(&locks);
 232             }
 233
 234             /* advance to next element in chain */
 235             previousNode = node;
 236             node         = node->next;
 237         }
 238     }
 239
 240     UNROLL_STACK(&locks);
 241
 242     /* not found */
 243     return IX_ETH_DB_NO_SUCH_ADDR;
 244 }
 245
 246 /**
 247  * @brief retrieves an entry from the hash table
 248  *
 249  * @param hashTable hash table to perform the search into
 250  * @param reference search key (a MAC address)
 251  * @param keyType type of record key used for matching
 252  * @param searchResult pointer where a reference to the located hash node
 253  * is placed
 254  *
 255  * Searches the entry with the same key as <i>reference</i> and places the
 256  * pointer to the resulting node in <i>searchResult</i>.
 257  * An implicit write access lock is granted after a search, which gives the
 258  * caller the opportunity to modify the entry.
 259  * Access should be released as soon as possible using @ref ixEthDBReleaseHashNode().
 260  *
 261  * @see ixEthDBReleaseHashNode()
 262  *
 263  * @retval IX_ETH_DB_SUCCESS if the search was completed successfully
 264  * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found
 265  * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case
 266  * the caller should retry
 267  *
 268  * @warning unless the return value is <b>IX_ETH_DB_SUCCESS</b> the searchResult
 269  * location is NOT modified and therefore using a NULL comparison test when the
 270  * value was not properly initialized would be an error
 271  *
 272  * @internal
 273  */
 274 IxEthDBStatus ixEthDBSearchHashEntry(HashTable *hashTable, int keyType, void *reference, HashNode **searchResult)
 275 {
 276     UINT32 hashValue;
 277     HashNode *node;
 278
 279     hashValue = hashTable->entryHashFunction(reference);
 280     node      = hashTable->hashBuckets[hashValue % hashTable->numBuckets];
 281
 282     while (node != NULL)
 283     {
 284         TRY_LOCK(&node->lock);
 285
 286         if (hashTable->matchFunctions[keyType](reference, node->data))
 287         {
 288             *searchResult = node;
 289
 290             return IX_ETH_DB_SUCCESS;
 291         }
 292         else
 293         {
 294             UNLOCK(&node->lock);
 295
 296             node = node->next;
 297         }
 298     }
 299
 300     /* not found */
 301     return IX_ETH_DB_NO_SUCH_ADDR;
 302 }
 303
 304 /**
 305  * @brief reports the existence of an entry in the hash table
 306  *
 307  * @param hashTable hash table to perform the search into
 308  * @param reference search key (a MAC address)
 309  * @param keyType type of record key used for matching
 310  *
 311  * Searches the entry with the same key as <i>reference</i>.
 312  * No implicit write access lock is granted after a search, hence the
 313  * caller cannot access or modify the entry. The result is only temporary.
 314  *
 315  * @see ixEthDBReleaseHashNode()
 316  *
 317  * @retval IX_ETH_DB_SUCCESS if the search was completed successfully
 318  * @retval IX_ETH_DB_NO_SUCH_ADDRESS if no entry with the given key was found
 319  * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case
 320  * the caller should retry
 321  *
 322  * @internal
 323  */
 324 IxEthDBStatus ixEthDBPeekHashEntry(HashTable *hashTable, int keyType, void *reference)
 325 {
 326     UINT32 hashValue;
 327     HashNode *node;
 328
 329     hashValue = hashTable->entryHashFunction(reference);
 330     node      = hashTable->hashBuckets[hashValue % hashTable->numBuckets];
 331
 332     while (node != NULL)
 333     {
 334         TRY_LOCK(&node->lock);
 335
 336         if (hashTable->matchFunctions[keyType](reference, node->data))
 337         {
 338             UNLOCK(&node->lock);
 339
 340             return IX_ETH_DB_SUCCESS;
 341         }
 342         else
 343         {
 344             UNLOCK(&node->lock);
 345
 346             node = node->next;
 347         }
 348     }
 349
 350     /* not found */
 351     return IX_ETH_DB_NO_SUCH_ADDR;
 352 }
 353
 354 /**
 355  * @brief releases the write access lock
 356  *
 357  * @pre the node should have been obtained via @ref ixEthDBSearchHashEntry()
 358  *
 359  * @see ixEthDBSearchHashEntry()
 360  *
 361  * @internal
 362  */
 363 void ixEthDBReleaseHashNode(HashNode *node)
 364 {
 365     UNLOCK(&node->lock);
 366 }
 367
 368 /**
 369  * @brief initializes a hash iterator
 370  *
 371  * @param hashTable hash table to be iterated
 372  * @param iterator iterator object
 373  *
 374  * If the initialization is successful the iterator will point to the
 375  * first hash table record (if any).
 376  * Testing if the iterator has not passed the end of the table should be
 377  * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
 378  * An implicit write access lock is granted on the entry pointed by the iterator.
 379  * The access is automatically revoked when the iterator is incremented.
 380  * If the caller decides to terminate the iteration before the end of the table is
 381  * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
 382  * must be called.
 383  *
 384  * @see ixEthDBReleaseHashIterator()
 385  *
 386  * @retval IX_ETH_DB_SUCCESS if initialization was successful and the iterator points
 387  * to the first valid table node
 388  * @retval IX_ETH_DB_FAIL if the table is empty
 389  * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
 390  * should retry
 391  *
 392  * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
 393  * might place the database in a permanent invalid lock state
 394  *
 395  * @internal
 396  */
 397 IxEthDBStatus ixEthDBInitHashIterator(HashTable *hashTable, HashIterator *iterator)
 398 {
 399     iterator->bucketIndex  = 0;
 400     iterator->node         = NULL;
 401     iterator->previousNode = NULL;
 402
 403     return ixEthDBIncrementHashIterator(hashTable, iterator);
 404 }
 405
 406 /**
 407  * @brief releases the write access locks of the iterator nodes
 408  *
 409  * @warning use of this function is required only when the caller terminates an iteration
 410  * before reaching the end of the table
 411  *
 412  * @see ixEthDBInitHashIterator()
 413  * @see ixEthDBIncrementHashIterator()
 414  *
 415  * @param iterator iterator whose node(s) should be unlocked
 416  *
 417  * @internal
 418  */
 419 void ixEthDBReleaseHashIterator(HashIterator *iterator)
 420 {
 421     if (iterator->previousNode != NULL)
 422     {
 423         UNLOCK(&iterator->previousNode->lock);
 424     }
 425
 426     if (iterator->node != NULL)
 427     {
 428         UNLOCK(&iterator->node->lock);
 429     }
 430 }
 431
 432 /**
 433  * @brief incremenents an iterator so that it points to the next valid entry of the table
 434  * (if any)
 435  *
 436  * @param hashTable hash table to iterate
 437  * @param iterator iterator object
 438  *
 439  * @pre the iterator object must be initialized using @ref ixEthDBInitHashIterator()
 440  *
 441  * If the increment operation is successful the iterator will point to the
 442  * next hash table record (if any).
 443  * Testing if the iterator has not passed the end of the table should be
 444  * done using the IS_ITERATOR_VALID(iteratorPtr) macro.
 445  * An implicit write access lock is granted on the entry pointed by the iterator.
 446  * The access is automatically revoked when the iterator is re-incremented.
 447  * If the caller decides to terminate the iteration before the end of the table is
 448  * passed then the manual access release method, @ref ixEthDBReleaseHashIterator,
 449  * must be called.
 450  * Is is guaranteed that no other thread can remove or change the iterated entry until
 451  * the iterator is incremented successfully.
 452  *
 453  * @see ixEthDBReleaseHashIterator()
 454  *
 455  * @retval IX_ETH_DB_SUCCESS if the operation was successful and the iterator points
 456  * to the next valid table node
 457  * @retval IX_ETH_DB_FAIL if the iterator has passed the end of the table
 458  * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
 459  * should retry
 460  *
 461  * @warning do not use ixEthDBReleaseHashNode() on entries pointed by the iterator, as this
 462  * might place the database in a permanent invalid lock state
 463  *
 464  * @internal
 465  */
 466 IxEthDBStatus ixEthDBIncrementHashIterator(HashTable *hashTable, HashIterator *iterator)
 467 {
 468     /* unless iterator is just initialized... */
 469     if (iterator->node != NULL)
 470     {
 471         /* try next in chain */
 472         if (iterator->node->next != NULL)
 473         {
 474             TRY_LOCK(&iterator->node->next->lock);
 475
 476             if (iterator->previousNode != NULL)
 477             {
 478                 UNLOCK(&iterator->previousNode->lock);
 479             }
 480
 481             iterator->previousNode = iterator->node;
 482             iterator->node         = iterator->node->next;
 483
 484             return IX_ETH_DB_SUCCESS;
 485         }
 486         else
 487         {
 488             /* last in chain, prepare for next bucket */
 489             iterator->bucketIndex++;
 490         }
 491     }
 492
 493    /* try next used bucket */
 494     for (; iterator->bucketIndex < hashTable->numBuckets ; iterator->bucketIndex++)
 495     {
 496         HashNode **nodePtr = &(hashTable->hashBuckets[iterator->bucketIndex]);
 497         HashNode *node = *nodePtr;
 498 #if (CPU!=SIMSPARCSOLARIS) && !defined (__wince)
 499         if (((iterator->bucketIndex & IX_ETHDB_BUCKET_INDEX_MASK) == 0) &&
 500             (iterator->bucketIndex < (hashTable->numBuckets - IX_ETHDB_BUCKETPTR_AHEAD)))
 501         {
 502             /* preload next cache line (2 cache line ahead) */
 503             nodePtr += IX_ETHDB_BUCKETPTR_AHEAD;
 504             __asm__ ("pld [%0];\n": : "r" (nodePtr));
 505         }
 506 #endif
 507         if (node != NULL)
 508         {
 509             TRY_LOCK(&node->lock);
 510
 511             /* unlock last one or two nodes in the previous chain */
 512             if (iterator->node != NULL)
 513             {
 514                 UNLOCK(&iterator->node->lock);
 515
 516                 if (iterator->previousNode != NULL)
 517                 {
 518                     UNLOCK(&iterator->previousNode->lock);
 519                 }
 520             }
 521
 522             /* redirect iterator */
 523             iterator->previousNode = NULL;
 524             iterator->node         = node;
 525
 526             return IX_ETH_DB_SUCCESS;
 527         }
 528     }
 529
 530     /* could not advance iterator */
 531     if (iterator->node != NULL)
 532     {
 533         UNLOCK(&iterator->node->lock);
 534
 535         if (iterator->previousNode != NULL)
 536         {
 537             UNLOCK(&iterator->previousNode->lock);
 538         }
 539
 540         iterator->node = NULL;
 541     }
 542
 543     return IX_ETH_DB_END;
 544 }
 545
 546 /**
 547  * @brief removes an entry pointed by an iterator
 548  *
 549  * @param hashTable iterated hash table
 550  * @param iterator iterator object
 551  *
 552  * Removes the entry currently pointed by the iterator and repositions the iterator
 553  * on the next valid entry (if any). Handles locking issues automatically and
 554  * implicitely grants write access lock to the new pointed entry.
 555  * Failures due to concurrent threads having write access locks in the same region
 556  * preserve the state of the database and the iterator object, leaving the caller
 557  * free to retry without loss of access. It is guaranteed that only the thread owning
 558  * the iterator can remove the object pointed by the iterator.
 559  *
 560  * @retval IX_ETH_DB_SUCCESS if removal has succeeded
 561  * @retval IX_ETH_DB_BUSY if a locking failure has occured, in which case the caller
 562  * should retry
 563  *
 564  * @internal
 565  */
 566 IxEthDBStatus ixEthDBRemoveEntryAtHashIterator(HashTable *hashTable, HashIterator *iterator)
 567 {
 568     HashIterator nextIteratorPos;
 569     LockStack locks;
 570
 571     INIT_STACK(&locks);
 572
 573     /* set initial bucket index for next position */
 574     nextIteratorPos.bucketIndex = iterator->bucketIndex;
 575
 576     /* compute iterator position before removing anything and lock ahead */
 577     if (iterator->node->next != NULL)
 578     {
 579         PUSH_LOCK(&locks, &iterator->node->next->lock);
 580
 581         /* reposition on the next node in the chain */
 582         nextIteratorPos.node         = iterator->node->next;
 583         nextIteratorPos.previousNode = iterator->previousNode;
 584     }
 585     else
 586     {
 587         /* try next chain - don't know yet if we'll find anything */
 588         nextIteratorPos.node = NULL;
 589
 590         /* if we find something it's a chain head */
 591         nextIteratorPos.previousNode = NULL;
 592
 593         /* browse up in the buckets to find a non-null chain */
 594         while (++nextIteratorPos.bucketIndex < hashTable->numBuckets)
 595         {
 596             nextIteratorPos.node = hashTable->hashBuckets[nextIteratorPos.bucketIndex];
 597
 598             if (nextIteratorPos.node != NULL)
 599             {
 600                 /* found a non-empty chain, try to lock head */
 601                 PUSH_LOCK(&locks, &nextIteratorPos.node->lock);
 602
 603                 break;
 604             }
 605         }
 606     }
 607
 608     /* restore links over the to-be-deleted item */
 609     if (iterator->previousNode == NULL)
 610     {
 611         /* first in chain, lock bucket */
 612         PUSH_LOCK(&locks, &hashTable->bucketLocks[iterator->bucketIndex]);
 613
 614         hashTable->hashBuckets[iterator->bucketIndex] = iterator->node->next;
 615
 616         POP_LOCK(&locks);
 617     }
 618     else
 619     {
 620         /* relink */
 621         iterator->previousNode->next = iterator->node->next;
 622
 623         /* unlock last remaining node in current chain when moving between chains */
 624         if (iterator->node->next == NULL)
 625         {
 626             UNLOCK(&iterator->previousNode->lock);
 627         }
 628     }
 629
 630     /* delete entry */
 631     hashTable->freeFunction(iterator->node->data);
 632     ixEthDBFreeHashNode(iterator->node);
 633
 634     /* reposition iterator */
 635     *iterator = nextIteratorPos;
 636
 637     return IX_ETH_DB_SUCCESS;
 638 }
 639
 640 /**
 641  * @}
 642  */