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