source: SVN/laguna/u-boot-2008.10/cpu/ixp/npe/IxEthDBHashtable.c @ 57

Last change on this file since 57 was 57, checked in by Tim Harvey, 3 years ago

Laguna: move prebuilt images and bootloader

svn directory cleanup

File size: 19.4 KB
Line 
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 */
70void 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 */
113IX_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 */
179IxEthDBStatus 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 */
274IxEthDBStatus 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 */
324IxEthDBStatus 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 */
363void 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 */
397IxEthDBStatus 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 */
419void 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 */
466IxEthDBStatus 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 */
566IxEthDBStatus 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 */
Note: See TracBrowser for help on using the repository browser.