~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/irda/irqueue.c

Version: ~ [ linux-5.9-rc6 ] ~ [ linux-5.8.10 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.66 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.146 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.198 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.236 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.236 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*********************************************************************
  2  *
  3  * Filename:      irqueue.c
  4  * Version:       0.3
  5  * Description:   General queue implementation
  6  * Status:        Experimental.
  7  * Author:        Dag Brattli <dagb@cs.uit.no>
  8  * Created at:    Tue Jun  9 13:29:31 1998
  9  * Modified at:   Sun Dec 12 13:48:22 1999
 10  * Modified by:   Dag Brattli <dagb@cs.uit.no>
 11  * Modified at:   Thu Jan  4 14:29:10 CET 2001
 12  * Modified by:   Marc Zyngier <mzyngier@freesurf.fr>
 13  *
 14  *     Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>
 15  *     Copyright (C) 1998, Dag Brattli,
 16  *     All Rights Reserved.
 17  *
 18  *     This code is taken from the Vortex Operating System written by Aage
 19  *     Kvalnes. Aage has agreed that this code can use the GPL licence,
 20  *     although he does not use that licence in his own code.
 21  *
 22  *     This copyright does however _not_ include the ELF hash() function
 23  *     which I currently don't know which licence or copyright it
 24  *     has. Please inform me if you know.
 25  *
 26  *     This program is free software; you can redistribute it and/or
 27  *     modify it under the terms of the GNU General Public License as
 28  *     published by the Free Software Foundation; either version 2 of
 29  *     the License, or (at your option) any later version.
 30  *
 31  *     Neither Dag Brattli nor University of Tromsø admit liability nor
 32  *     provide warranty for any of this software. This material is
 33  *     provided "AS-IS" and at no charge.
 34  *
 35  ********************************************************************/
 36 
 37 /*
 38  * NOTE :
 39  * There are various problems with this package :
 40  *      o the hash function for ints is pathetic (but could be changed)
 41  *      o locking is sometime suspicious (especially during enumeration)
 42  *      o most users have only a few elements (== overhead)
 43  *      o most users never use search, so don't benefit from hashing
 44  * Problem already fixed :
 45  *      o not 64 bit compliant (most users do hashv = (int) self)
 46  *      o hashbin_remove() is broken => use hashbin_remove_this()
 47  * I think most users would be better served by a simple linked list
 48  * (like include/linux/list.h) with a global spinlock per list.
 49  * Jean II
 50  */
 51 
 52 /*
 53  * Notes on the concurrent access to hashbin and other SMP issues
 54  * -------------------------------------------------------------
 55  *      Hashbins are very often in the IrDA stack a global repository of
 56  * information, and therefore used in a very asynchronous manner following
 57  * various events (driver calls, timers, user calls...).
 58  *      Therefore, very often it is highly important to consider the
 59  * management of concurrent access to the hashbin and how to guarantee the
 60  * consistency of the operations on it.
 61  *
 62  *      First, we need to define the objective of locking :
 63  *              1) Protect user data (content pointed by the hashbin)
 64  *              2) Protect hashbin structure itself (linked list in each bin)
 65  *
 66  *                           OLD LOCKING
 67  *                           -----------
 68  *
 69  *      The previous locking strategy, either HB_LOCAL or HB_GLOBAL were
 70  * both inadequate in *both* aspect.
 71  *              o HB_GLOBAL was using a spinlock for each bin (local locking).
 72  *              o HB_LOCAL was disabling irq on *all* CPUs, so use a single
 73  *                global semaphore.
 74  *      The problems were :
 75  *              A) Global irq disabling is no longer supported by the kernel
 76  *              B) No protection for the hashbin struct global data
 77  *                      o hashbin_delete()
 78  *                      o hb_current
 79  *              C) No protection for user data in some cases
 80  *
 81  *      A) HB_LOCAL use global irq disabling, so doesn't work on kernel
 82  * 2.5.X. Even when it is supported (kernel 2.4.X and earlier), its
 83  * performance is not satisfactory on SMP setups. Most hashbins were
 84  * HB_LOCAL, so (A) definitely need fixing.
 85  *      B) HB_LOCAL could be modified to fix (B). However, because HB_GLOBAL
 86  * lock only the individual bins, it will never be able to lock the
 87  * global data, so can't do (B).
 88  *      C) Some functions return pointer to data that is still in the
 89  * hashbin :
 90  *              o hashbin_find()
 91  *              o hashbin_get_first()
 92  *              o hashbin_get_next()
 93  *      As the data is still in the hashbin, it may be changed or free'd
 94  * while the caller is examinimg the data. In those case, locking can't
 95  * be done within the hashbin, but must include use of the data within
 96  * the caller.
 97  *      The caller can easily do this with HB_LOCAL (just disable irqs).
 98  * However, this is impossible with HB_GLOBAL because the caller has no
 99  * way to know the proper bin, so don't know which spinlock to use.
100  *
101  *      Quick summary : can no longer use HB_LOCAL, and HB_GLOBAL is
102  * fundamentally broken and will never work.
103  *
104  *                           NEW LOCKING
105  *                           -----------
106  *
107  *      To fix those problems, I've introduce a few changes in the
108  * hashbin locking :
109  *              1) New HB_LOCK scheme
110  *              2) hashbin->hb_spinlock
111  *              3) New hashbin usage policy
112  *
113  * HB_LOCK :
114  * -------
115  *      HB_LOCK is a locking scheme intermediate between the old HB_LOCAL
116  * and HB_GLOBAL. It uses a single spinlock to protect the whole content
117  * of the hashbin. As it is a single spinlock, it can protect the global
118  * data of the hashbin and not only the bins themselves.
119  *      HB_LOCK can only protect some of the hashbin calls, so it only lock
120  * call that can be made 100% safe and leave other call unprotected.
121  *      HB_LOCK in theory is slower than HB_GLOBAL, but as the hashbin
122  * content is always small contention is not high, so it doesn't matter
123  * much. HB_LOCK is probably faster than HB_LOCAL.
124  *
125  * hashbin->hb_spinlock :
126  * --------------------
127  *      The spinlock that HB_LOCK uses is available for caller, so that
128  * the caller can protect unprotected calls (see below).
129  *      If the caller want to do entirely its own locking (HB_NOLOCK), he
130  * can do so and may use safely this spinlock.
131  *      Locking is done like this :
132  *              spin_lock_irqsave(&hashbin->hb_spinlock, flags);
133  *      Releasing the lock :
134  *              spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
135  *
136  * Safe & Protected calls :
137  * ----------------------
138  *      The following calls are safe or protected via HB_LOCK :
139  *              o hashbin_new()         -> safe
140  *              o hashbin_delete()
141  *              o hashbin_insert()
142  *              o hashbin_remove_first()
143  *              o hashbin_remove()
144  *              o hashbin_remove_this()
145  *              o HASHBIN_GET_SIZE()    -> atomic
146  *
147  *      The following calls only protect the hashbin itself :
148  *              o hashbin_lock_find()
149  *              o hashbin_find_next()
150  *
151  * Unprotected calls :
152  * -----------------
153  *      The following calls need to be protected by the caller :
154  *              o hashbin_find()
155  *              o hashbin_get_first()
156  *              o hashbin_get_next()
157  *
158  * Locking Policy :
159  * --------------
160  *      If the hashbin is used only in a single thread of execution
161  * (explicitly or implicitely), you can use HB_NOLOCK
162  *      If the calling module already provide concurrent access protection,
163  * you may use HB_NOLOCK.
164  *
165  *      In all other cases, you need to use HB_LOCK and lock the hashbin
166  * every time before calling one of the unprotected calls. You also must
167  * use the pointer returned by the unprotected call within the locked
168  * region.
169  *
170  * Extra care for enumeration :
171  * --------------------------
172  *      hashbin_get_first() and hashbin_get_next() use the hashbin to
173  * store the current position, in hb_current.
174  *      As long as the hashbin remains locked, this is safe. If you unlock
175  * the hashbin, the current position may change if anybody else modify
176  * or enumerate the hashbin.
177  *      Summary : do the full enumeration while locked.
178  *
179  *      Alternatively, you may use hashbin_find_next(). But, this will
180  * be slower, is more complex to use and doesn't protect the hashbin
181  * content. So, care is needed here as well.
182  *
183  * Other issues :
184  * ------------
185  *      I believe that we are overdoing it by using spin_lock_irqsave()
186  * and we should use only spin_lock_bh() or similar. But, I don't have
187  * the balls to try it out.
188  *      Don't believe that because hashbin are now (somewhat) SMP safe
189  * that the rest of the code is. Higher layers tend to be safest,
190  * but LAP and LMP would need some serious dedicated love.
191  *
192  * Jean II
193  */
194 #include <linux/module.h>
195 #include <linux/slab.h>
196 
197 #include <net/irda/irda.h>
198 #include <net/irda/irqueue.h>
199 
200 /************************ QUEUE SUBROUTINES ************************/
201 
202 /*
203  * Hashbin
204  */
205 #define GET_HASHBIN(x) ( x & HASHBIN_MASK )
206 
207 /*
208  * Function hash (name)
209  *
210  *    This function hash the input string 'name' using the ELF hash
211  *    function for strings.
212  */
213 static __u32 hash( const char* name)
214 {
215         __u32 h = 0;
216         __u32 g;
217 
218         while(*name) {
219                 h = (h<<4) + *name++;
220                 if ((g = (h & 0xf0000000)))
221                         h ^=g>>24;
222                 h &=~g;
223         }
224         return h;
225 }
226 
227 /*
228  * Function enqueue_first (queue, proc)
229  *
230  *    Insert item first in queue.
231  *
232  */
233 static void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
234 {
235 
236         IRDA_DEBUG( 4, "%s()\n", __func__);
237 
238         /*
239          * Check if queue is empty.
240          */
241         if ( *queue == NULL ) {
242                 /*
243                  * Queue is empty.  Insert one element into the queue.
244                  */
245                 element->q_next = element->q_prev = *queue = element;
246 
247         } else {
248                 /*
249                  * Queue is not empty.  Insert element into front of queue.
250                  */
251                 element->q_next          = (*queue);
252                 (*queue)->q_prev->q_next = element;
253                 element->q_prev          = (*queue)->q_prev;
254                 (*queue)->q_prev         = element;
255                 (*queue)                 = element;
256         }
257 }
258 
259 
260 /*
261  * Function dequeue (queue)
262  *
263  *    Remove first entry in queue
264  *
265  */
266 static irda_queue_t *dequeue_first(irda_queue_t **queue)
267 {
268         irda_queue_t *ret;
269 
270         IRDA_DEBUG( 4, "dequeue_first()\n");
271 
272         /*
273          * Set return value
274          */
275         ret =  *queue;
276 
277         if ( *queue == NULL ) {
278                 /*
279                  * Queue was empty.
280                  */
281         } else if ( (*queue)->q_next == *queue ) {
282                 /*
283                  *  Queue only contained a single element. It will now be
284                  *  empty.
285                  */
286                 *queue = NULL;
287         } else {
288                 /*
289                  * Queue contained several element.  Remove the first one.
290                  */
291                 (*queue)->q_prev->q_next = (*queue)->q_next;
292                 (*queue)->q_next->q_prev = (*queue)->q_prev;
293                 *queue = (*queue)->q_next;
294         }
295 
296         /*
297          * Return the removed entry (or NULL of queue was empty).
298          */
299         return ret;
300 }
301 
302 /*
303  * Function dequeue_general (queue, element)
304  *
305  *
306  */
307 static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element)
308 {
309         irda_queue_t *ret;
310 
311         IRDA_DEBUG( 4, "dequeue_general()\n");
312 
313         /*
314          * Set return value
315          */
316         ret =  *queue;
317 
318         if ( *queue == NULL ) {
319                 /*
320                  * Queue was empty.
321                  */
322         } else if ( (*queue)->q_next == *queue ) {
323                 /*
324                  *  Queue only contained a single element. It will now be
325                  *  empty.
326                  */
327                 *queue = NULL;
328 
329         } else {
330                 /*
331                  *  Remove specific element.
332                  */
333                 element->q_prev->q_next = element->q_next;
334                 element->q_next->q_prev = element->q_prev;
335                 if ( (*queue) == element)
336                         (*queue) = element->q_next;
337         }
338 
339         /*
340          * Return the removed entry (or NULL of queue was empty).
341          */
342         return ret;
343 }
344 
345 /************************ HASHBIN MANAGEMENT ************************/
346 
347 /*
348  * Function hashbin_create ( type, name )
349  *
350  *    Create hashbin!
351  *
352  */
353 hashbin_t *hashbin_new(int type)
354 {
355         hashbin_t* hashbin;
356 
357         /*
358          * Allocate new hashbin
359          */
360         hashbin = kzalloc(sizeof(*hashbin), GFP_ATOMIC);
361         if (!hashbin)
362                 return NULL;
363 
364         /*
365          * Initialize structure
366          */
367         hashbin->hb_type = type;
368         hashbin->magic = HB_MAGIC;
369         //hashbin->hb_current = NULL;
370 
371         /* Make sure all spinlock's are unlocked */
372         if ( hashbin->hb_type & HB_LOCK ) {
373                 spin_lock_init(&hashbin->hb_spinlock);
374         }
375 
376         return hashbin;
377 }
378 EXPORT_SYMBOL(hashbin_new);
379 
380 
381 /*
382  * Function hashbin_delete (hashbin, free_func)
383  *
384  *    Destroy hashbin, the free_func can be a user supplied special routine
385  *    for deallocating this structure if it's complex. If not the user can
386  *    just supply kfree, which should take care of the job.
387  */
388 #ifdef CONFIG_LOCKDEP
389 static int hashbin_lock_depth = 0;
390 #endif
391 int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
392 {
393         irda_queue_t* queue;
394         unsigned long flags = 0;
395         int i;
396 
397         IRDA_ASSERT(hashbin != NULL, return -1;);
398         IRDA_ASSERT(hashbin->magic == HB_MAGIC, return -1;);
399 
400         /* Synchronize */
401         if ( hashbin->hb_type & HB_LOCK ) {
402                 spin_lock_irqsave_nested(&hashbin->hb_spinlock, flags,
403                                          hashbin_lock_depth++);
404         }
405 
406         /*
407          *  Free the entries in the hashbin, TODO: use hashbin_clear when
408          *  it has been shown to work
409          */
410         for (i = 0; i < HASHBIN_SIZE; i ++ ) {
411                 queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);
412                 while (queue ) {
413                         if (free_func)
414                                 (*free_func)(queue);
415                         queue = dequeue_first(
416                                 (irda_queue_t**) &hashbin->hb_queue[i]);
417                 }
418         }
419 
420         /* Cleanup local data */
421         hashbin->hb_current = NULL;
422         hashbin->magic = ~HB_MAGIC;
423 
424         /* Release lock */
425         if ( hashbin->hb_type & HB_LOCK) {
426                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
427 #ifdef CONFIG_LOCKDEP
428                 hashbin_lock_depth--;
429 #endif
430         }
431 
432         /*
433          *  Free the hashbin structure
434          */
435         kfree(hashbin);
436 
437         return 0;
438 }
439 EXPORT_SYMBOL(hashbin_delete);
440 
441 /********************* HASHBIN LIST OPERATIONS *********************/
442 
443 /*
444  * Function hashbin_insert (hashbin, entry, name)
445  *
446  *    Insert an entry into the hashbin
447  *
448  */
449 void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, long hashv,
450                     const char* name)
451 {
452         unsigned long flags = 0;
453         int bin;
454 
455         IRDA_DEBUG( 4, "%s()\n", __func__);
456 
457         IRDA_ASSERT( hashbin != NULL, return;);
458         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return;);
459 
460         /*
461          * Locate hashbin
462          */
463         if ( name )
464                 hashv = hash( name );
465         bin = GET_HASHBIN( hashv );
466 
467         /* Synchronize */
468         if ( hashbin->hb_type & HB_LOCK ) {
469                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
470         } /* Default is no-lock  */
471 
472         /*
473          * Store name and key
474          */
475         entry->q_hash = hashv;
476         if ( name )
477                 strlcpy( entry->q_name, name, sizeof(entry->q_name));
478 
479         /*
480          * Insert new entry first
481          */
482         enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
483                        entry);
484         hashbin->hb_size++;
485 
486         /* Release lock */
487         if ( hashbin->hb_type & HB_LOCK ) {
488                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
489         } /* Default is no-lock  */
490 }
491 EXPORT_SYMBOL(hashbin_insert);
492 
493 /*
494  *  Function hashbin_remove_first (hashbin)
495  *
496  *    Remove first entry of the hashbin
497  *
498  * Note : this function no longer use hashbin_remove(), but does things
499  * similar to hashbin_remove_this(), so can be considered safe.
500  * Jean II
501  */
502 void *hashbin_remove_first( hashbin_t *hashbin)
503 {
504         unsigned long flags = 0;
505         irda_queue_t *entry = NULL;
506 
507         /* Synchronize */
508         if ( hashbin->hb_type & HB_LOCK ) {
509                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
510         } /* Default is no-lock  */
511 
512         entry = hashbin_get_first( hashbin);
513         if ( entry != NULL) {
514                 int     bin;
515                 long    hashv;
516                 /*
517                  * Locate hashbin
518                  */
519                 hashv = entry->q_hash;
520                 bin = GET_HASHBIN( hashv );
521 
522                 /*
523                  * Dequeue the entry...
524                  */
525                 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
526                                  entry);
527                 hashbin->hb_size--;
528                 entry->q_next = NULL;
529                 entry->q_prev = NULL;
530 
531                 /*
532                  *  Check if this item is the currently selected item, and in
533                  *  that case we must reset hb_current
534                  */
535                 if ( entry == hashbin->hb_current)
536                         hashbin->hb_current = NULL;
537         }
538 
539         /* Release lock */
540         if ( hashbin->hb_type & HB_LOCK ) {
541                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
542         } /* Default is no-lock  */
543 
544         return entry;
545 }
546 
547 
548 /*
549  *  Function hashbin_remove (hashbin, hashv, name)
550  *
551  *    Remove entry with the given name
552  *
553  *  The use of this function is highly discouraged, because the whole
554  *  concept behind hashbin_remove() is broken. In many cases, it's not
555  *  possible to guarantee the unicity of the index (either hashv or name),
556  *  leading to removing the WRONG entry.
557  *  The only simple safe use is :
558  *              hashbin_remove(hasbin, (int) self, NULL);
559  *  In other case, you must think hard to guarantee unicity of the index.
560  *  Jean II
561  */
562 void* hashbin_remove( hashbin_t* hashbin, long hashv, const char* name)
563 {
564         int bin, found = FALSE;
565         unsigned long flags = 0;
566         irda_queue_t* entry;
567 
568         IRDA_DEBUG( 4, "%s()\n", __func__);
569 
570         IRDA_ASSERT( hashbin != NULL, return NULL;);
571         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
572 
573         /*
574          * Locate hashbin
575          */
576         if ( name )
577                 hashv = hash( name );
578         bin = GET_HASHBIN( hashv );
579 
580         /* Synchronize */
581         if ( hashbin->hb_type & HB_LOCK ) {
582                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
583         } /* Default is no-lock  */
584 
585         /*
586          * Search for entry
587          */
588         entry = hashbin->hb_queue[ bin ];
589         if ( entry ) {
590                 do {
591                         /*
592                          * Check for key
593                          */
594                         if ( entry->q_hash == hashv ) {
595                                 /*
596                                  * Name compare too?
597                                  */
598                                 if ( name ) {
599                                         if ( strcmp( entry->q_name, name) == 0)
600                                         {
601                                                 found = TRUE;
602                                                 break;
603                                         }
604                                 } else {
605                                         found = TRUE;
606                                         break;
607                                 }
608                         }
609                         entry = entry->q_next;
610                 } while ( entry != hashbin->hb_queue[ bin ] );
611         }
612 
613         /*
614          * If entry was found, dequeue it
615          */
616         if ( found ) {
617                 dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
618                                  entry);
619                 hashbin->hb_size--;
620 
621                 /*
622                  *  Check if this item is the currently selected item, and in
623                  *  that case we must reset hb_current
624                  */
625                 if ( entry == hashbin->hb_current)
626                         hashbin->hb_current = NULL;
627         }
628 
629         /* Release lock */
630         if ( hashbin->hb_type & HB_LOCK ) {
631                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
632         } /* Default is no-lock  */
633 
634 
635         /* Return */
636         if ( found )
637                 return entry;
638         else
639                 return NULL;
640 
641 }
642 EXPORT_SYMBOL(hashbin_remove);
643 
644 /*
645  *  Function hashbin_remove_this (hashbin, entry)
646  *
647  *    Remove entry with the given name
648  *
649  * In some cases, the user of hashbin can't guarantee the unicity
650  * of either the hashv or name.
651  * In those cases, using the above function is guaranteed to cause troubles,
652  * so we use this one instead...
653  * And by the way, it's also faster, because we skip the search phase ;-)
654  */
655 void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
656 {
657         unsigned long flags = 0;
658         int     bin;
659         long    hashv;
660 
661         IRDA_DEBUG( 4, "%s()\n", __func__);
662 
663         IRDA_ASSERT( hashbin != NULL, return NULL;);
664         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
665         IRDA_ASSERT( entry != NULL, return NULL;);
666 
667         /* Synchronize */
668         if ( hashbin->hb_type & HB_LOCK ) {
669                 spin_lock_irqsave(&hashbin->hb_spinlock, flags);
670         } /* Default is no-lock  */
671 
672         /* Check if valid and not already removed... */
673         if((entry->q_next == NULL) || (entry->q_prev == NULL)) {
674                 entry = NULL;
675                 goto out;
676         }
677 
678         /*
679          * Locate hashbin
680          */
681         hashv = entry->q_hash;
682         bin = GET_HASHBIN( hashv );
683 
684         /*
685          * Dequeue the entry...
686          */
687         dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
688                          entry);
689         hashbin->hb_size--;
690         entry->q_next = NULL;
691         entry->q_prev = NULL;
692 
693         /*
694          *  Check if this item is the currently selected item, and in
695          *  that case we must reset hb_current
696          */
697         if ( entry == hashbin->hb_current)
698                 hashbin->hb_current = NULL;
699 out:
700         /* Release lock */
701         if ( hashbin->hb_type & HB_LOCK ) {
702                 spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
703         } /* Default is no-lock  */
704 
705         return entry;
706 }
707 EXPORT_SYMBOL(hashbin_remove_this);
708 
709 /*********************** HASHBIN ENUMERATION ***********************/
710 
711 /*
712  * Function hashbin_common_find (hashbin, hashv, name)
713  *
714  *    Find item with the given hashv or name
715  *
716  */
717 void* hashbin_find( hashbin_t* hashbin, long hashv, const char* name )
718 {
719         int bin;
720         irda_queue_t* entry;
721 
722         IRDA_DEBUG( 4, "hashbin_find()\n");
723 
724         IRDA_ASSERT( hashbin != NULL, return NULL;);
725         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
726 
727         /*
728          * Locate hashbin
729          */
730         if ( name )
731                 hashv = hash( name );
732         bin = GET_HASHBIN( hashv );
733 
734         /*
735          * Search for entry
736          */
737         entry = hashbin->hb_queue[ bin];
738         if ( entry ) {
739                 do {
740                         /*
741                          * Check for key
742                          */
743                         if ( entry->q_hash == hashv ) {
744                                 /*
745                                  * Name compare too?
746                                  */
747                                 if ( name ) {
748                                         if ( strcmp( entry->q_name, name ) == 0 ) {
749                                                 return entry;
750                                         }
751                                 } else {
752                                         return entry;
753                                 }
754                         }
755                         entry = entry->q_next;
756                 } while ( entry != hashbin->hb_queue[ bin ] );
757         }
758 
759         return NULL;
760 }
761 EXPORT_SYMBOL(hashbin_find);
762 
763 /*
764  * Function hashbin_lock_find (hashbin, hashv, name)
765  *
766  *    Find item with the given hashv or name
767  *
768  * Same, but with spinlock protection...
769  * I call it safe, but it's only safe with respect to the hashbin, not its
770  * content. - Jean II
771  */
772 void* hashbin_lock_find( hashbin_t* hashbin, long hashv, const char* name )
773 {
774         unsigned long flags = 0;
775         irda_queue_t* entry;
776 
777         /* Synchronize */
778         spin_lock_irqsave(&hashbin->hb_spinlock, flags);
779 
780         /*
781          * Search for entry
782          */
783         entry = hashbin_find(hashbin, hashv, name);
784 
785         /* Release lock */
786         spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
787 
788         return entry;
789 }
790 EXPORT_SYMBOL(hashbin_lock_find);
791 
792 /*
793  * Function hashbin_find (hashbin, hashv, name, pnext)
794  *
795  *    Find an item with the given hashv or name, and its successor
796  *
797  * This function allow to do concurrent enumerations without the
798  * need to lock over the whole session, because the caller keep the
799  * context of the search. On the other hand, it might fail and return
800  * NULL if the entry is removed. - Jean II
801  */
802 void* hashbin_find_next( hashbin_t* hashbin, long hashv, const char* name,
803                          void ** pnext)
804 {
805         unsigned long flags = 0;
806         irda_queue_t* entry;
807 
808         /* Synchronize */
809         spin_lock_irqsave(&hashbin->hb_spinlock, flags);
810 
811         /*
812          * Search for current entry
813          * This allow to check if the current item is still in the
814          * hashbin or has been removed.
815          */
816         entry = hashbin_find(hashbin, hashv, name);
817 
818         /*
819          * Trick hashbin_get_next() to return what we want
820          */
821         if(entry) {
822                 hashbin->hb_current = entry;
823                 *pnext = hashbin_get_next( hashbin );
824         } else
825                 *pnext = NULL;
826 
827         /* Release lock */
828         spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
829 
830         return entry;
831 }
832 
833 /*
834  * Function hashbin_get_first (hashbin)
835  *
836  *    Get a pointer to first element in hashbin, this function must be
837  *    called before any calls to hashbin_get_next()!
838  *
839  */
840 irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
841 {
842         irda_queue_t *entry;
843         int i;
844 
845         IRDA_ASSERT( hashbin != NULL, return NULL;);
846         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
847 
848         if ( hashbin == NULL)
849                 return NULL;
850 
851         for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
852                 entry = hashbin->hb_queue[ i];
853                 if ( entry) {
854                         hashbin->hb_current = entry;
855                         return entry;
856                 }
857         }
858         /*
859          *  Did not find any item in hashbin
860          */
861         return NULL;
862 }
863 EXPORT_SYMBOL(hashbin_get_first);
864 
865 /*
866  * Function hashbin_get_next (hashbin)
867  *
868  *    Get next item in hashbin. A series of hashbin_get_next() calls must
869  *    be started by a call to hashbin_get_first(). The function returns
870  *    NULL when all items have been traversed
871  *
872  * The context of the search is stored within the hashbin, so you must
873  * protect yourself from concurrent enumerations. - Jean II
874  */
875 irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
876 {
877         irda_queue_t* entry;
878         int bin;
879         int i;
880 
881         IRDA_ASSERT( hashbin != NULL, return NULL;);
882         IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
883 
884         if ( hashbin->hb_current == NULL) {
885                 IRDA_ASSERT( hashbin->hb_current != NULL, return NULL;);
886                 return NULL;
887         }
888         entry = hashbin->hb_current->q_next;
889         bin = GET_HASHBIN( entry->q_hash);
890 
891         /*
892          *  Make sure that we are not back at the beginning of the queue
893          *  again
894          */
895         if ( entry != hashbin->hb_queue[ bin ]) {
896                 hashbin->hb_current = entry;
897 
898                 return entry;
899         }
900 
901         /*
902          *  Check that this is not the last queue in hashbin
903          */
904         if ( bin >= HASHBIN_SIZE)
905                 return NULL;
906 
907         /*
908          *  Move to next queue in hashbin
909          */
910         bin++;
911         for ( i = bin; i < HASHBIN_SIZE; i++ ) {
912                 entry = hashbin->hb_queue[ i];
913                 if ( entry) {
914                         hashbin->hb_current = entry;
915 
916                         return entry;
917                 }
918         }
919         return NULL;
920 }
921 EXPORT_SYMBOL(hashbin_get_next);
922 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp