IxEthDBHashtable.c 18 KB

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