1 /*********************************************************************
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>
14 * Copyright (C) 1998-1999, Aage Kvalnes <aage@cs.uit.no>
15 * Copyright (C) 1998, Dag Brattli,
16 * All Rights Reserved.
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.
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.
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.
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.
35 ********************************************************************/
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 seach, 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.
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.
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)
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
75 * A) Global irq disabling is no longer supported by the kernel
76 * B) No protection for the hashbin struct global data
79 * C) No protection for user data in some cases
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
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
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.
101 * Quick summary : can no longer use HB_LOCAL, and HB_GLOBAL is
102 * fundamentally broken and will never work.
107 * To fix those problems, I've introduce a few changes in the
109 * 1) New HB_LOCK scheme
110 * 2) hashbin->hb_spinlock
111 * 3) New hashbin usage policy
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.
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);
136 * Safe & Protected calls :
137 * ----------------------
138 * The following calls are safe or protected via HB_LOCK :
139 * o hashbin_new() -> safe
142 * o hashbin_remove_first()
144 * o hashbin_remove_this()
145 * o HASHBIN_GET_SIZE() -> atomic
147 * The following calls only protect the hashbin itself :
148 * o hashbin_lock_find()
149 * o hashbin_find_next()
151 * Unprotected calls :
153 * The following calls need to be protected by the caller :
155 * o hashbin_get_first()
156 * o hashbin_get_next()
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.
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
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.
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.
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.
194 #include <linux/module.h>
196 #include <net/irda/irda.h>
197 #include <net/irda/irqueue.h>
199 /************************ QUEUE SUBROUTINES ************************/
204 #define GET_HASHBIN(x) ( x & HASHBIN_MASK )
207 * Function hash (name)
209 * This function hash the input string 'name' using the ELF hash
210 * function for strings.
212 static __u32
hash( const char* name
)
218 h
= (h
<<4) + *name
++;
219 if ((g
= (h
& 0xf0000000)))
227 * Function enqueue_first (queue, proc)
229 * Insert item first in queue.
232 static void enqueue_first(irda_queue_t
**queue
, irda_queue_t
* element
)
235 IRDA_DEBUG( 4, "%s()\n", __func__
);
238 * Check if queue is empty.
240 if ( *queue
== NULL
) {
242 * Queue is empty. Insert one element into the queue.
244 element
->q_next
= element
->q_prev
= *queue
= element
;
248 * Queue is not empty. Insert element into front of queue.
250 element
->q_next
= (*queue
);
251 (*queue
)->q_prev
->q_next
= element
;
252 element
->q_prev
= (*queue
)->q_prev
;
253 (*queue
)->q_prev
= element
;
260 * Function dequeue (queue)
262 * Remove first entry in queue
265 static irda_queue_t
*dequeue_first(irda_queue_t
**queue
)
269 IRDA_DEBUG( 4, "dequeue_first()\n");
276 if ( *queue
== NULL
) {
280 } else if ( (*queue
)->q_next
== *queue
) {
282 * Queue only contained a single element. It will now be
288 * Queue contained several element. Remove the first one.
290 (*queue
)->q_prev
->q_next
= (*queue
)->q_next
;
291 (*queue
)->q_next
->q_prev
= (*queue
)->q_prev
;
292 *queue
= (*queue
)->q_next
;
296 * Return the removed entry (or NULL of queue was empty).
302 * Function dequeue_general (queue, element)
306 static irda_queue_t
*dequeue_general(irda_queue_t
**queue
, irda_queue_t
* element
)
310 IRDA_DEBUG( 4, "dequeue_general()\n");
317 if ( *queue
== NULL
) {
321 } else if ( (*queue
)->q_next
== *queue
) {
323 * Queue only contained a single element. It will now be
330 * Remove specific element.
332 element
->q_prev
->q_next
= element
->q_next
;
333 element
->q_next
->q_prev
= element
->q_prev
;
334 if ( (*queue
) == element
)
335 (*queue
) = element
->q_next
;
339 * Return the removed entry (or NULL of queue was empty).
344 /************************ HASHBIN MANAGEMENT ************************/
347 * Function hashbin_create ( type, name )
352 hashbin_t
*hashbin_new(int type
)
357 * Allocate new hashbin
359 hashbin
= kzalloc(sizeof(*hashbin
), GFP_ATOMIC
);
364 * Initialize structure
366 hashbin
->hb_type
= type
;
367 hashbin
->magic
= HB_MAGIC
;
368 //hashbin->hb_current = NULL;
370 /* Make sure all spinlock's are unlocked */
371 if ( hashbin
->hb_type
& HB_LOCK
) {
372 spin_lock_init(&hashbin
->hb_spinlock
);
377 EXPORT_SYMBOL(hashbin_new
);
381 * Function hashbin_delete (hashbin, free_func)
383 * Destroy hashbin, the free_func can be a user supplied special routine
384 * for deallocating this structure if it's complex. If not the user can
385 * just supply kfree, which should take care of the job.
387 #ifdef CONFIG_LOCKDEP
388 static int hashbin_lock_depth
= 0;
390 int hashbin_delete( hashbin_t
* hashbin
, FREE_FUNC free_func
)
393 unsigned long flags
= 0;
396 IRDA_ASSERT(hashbin
!= NULL
, return -1;);
397 IRDA_ASSERT(hashbin
->magic
== HB_MAGIC
, return -1;);
400 if ( hashbin
->hb_type
& HB_LOCK
) {
401 spin_lock_irqsave_nested(&hashbin
->hb_spinlock
, flags
,
402 hashbin_lock_depth
++);
406 * Free the entries in the hashbin, TODO: use hashbin_clear when
407 * it has been shown to work
409 for (i
= 0; i
< HASHBIN_SIZE
; i
++ ) {
410 queue
= dequeue_first((irda_queue_t
**) &hashbin
->hb_queue
[i
]);
414 queue
= dequeue_first(
415 (irda_queue_t
**) &hashbin
->hb_queue
[i
]);
419 /* Cleanup local data */
420 hashbin
->hb_current
= NULL
;
421 hashbin
->magic
= ~HB_MAGIC
;
424 if ( hashbin
->hb_type
& HB_LOCK
) {
425 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
426 #ifdef CONFIG_LOCKDEP
427 hashbin_lock_depth
--;
432 * Free the hashbin structure
438 EXPORT_SYMBOL(hashbin_delete
);
440 /********************* HASHBIN LIST OPERATIONS *********************/
443 * Function hashbin_insert (hashbin, entry, name)
445 * Insert an entry into the hashbin
448 void hashbin_insert(hashbin_t
* hashbin
, irda_queue_t
* entry
, long hashv
,
451 unsigned long flags
= 0;
454 IRDA_DEBUG( 4, "%s()\n", __func__
);
456 IRDA_ASSERT( hashbin
!= NULL
, return;);
457 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return;);
463 hashv
= hash( name
);
464 bin
= GET_HASHBIN( hashv
);
467 if ( hashbin
->hb_type
& HB_LOCK
) {
468 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
469 } /* Default is no-lock */
474 entry
->q_hash
= hashv
;
476 strlcpy( entry
->q_name
, name
, sizeof(entry
->q_name
));
479 * Insert new entry first
481 enqueue_first( (irda_queue_t
**) &hashbin
->hb_queue
[ bin
],
486 if ( hashbin
->hb_type
& HB_LOCK
) {
487 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
488 } /* Default is no-lock */
490 EXPORT_SYMBOL(hashbin_insert
);
493 * Function hashbin_remove_first (hashbin)
495 * Remove first entry of the hashbin
497 * Note : this function no longer use hashbin_remove(), but does things
498 * similar to hashbin_remove_this(), so can be considered safe.
501 void *hashbin_remove_first( hashbin_t
*hashbin
)
503 unsigned long flags
= 0;
504 irda_queue_t
*entry
= NULL
;
507 if ( hashbin
->hb_type
& HB_LOCK
) {
508 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
509 } /* Default is no-lock */
511 entry
= hashbin_get_first( hashbin
);
512 if ( entry
!= NULL
) {
518 hashv
= entry
->q_hash
;
519 bin
= GET_HASHBIN( hashv
);
522 * Dequeue the entry...
524 dequeue_general( (irda_queue_t
**) &hashbin
->hb_queue
[ bin
],
525 (irda_queue_t
*) entry
);
527 entry
->q_next
= NULL
;
528 entry
->q_prev
= NULL
;
531 * Check if this item is the currently selected item, and in
532 * that case we must reset hb_current
534 if ( entry
== hashbin
->hb_current
)
535 hashbin
->hb_current
= NULL
;
539 if ( hashbin
->hb_type
& HB_LOCK
) {
540 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
541 } /* Default is no-lock */
548 * Function hashbin_remove (hashbin, hashv, name)
550 * Remove entry with the given name
552 * The use of this function is highly discouraged, because the whole
553 * concept behind hashbin_remove() is broken. In many cases, it's not
554 * possible to guarantee the unicity of the index (either hashv or name),
555 * leading to removing the WRONG entry.
556 * The only simple safe use is :
557 * hashbin_remove(hasbin, (int) self, NULL);
558 * In other case, you must think hard to guarantee unicity of the index.
561 void* hashbin_remove( hashbin_t
* hashbin
, long hashv
, const char* name
)
563 int bin
, found
= FALSE
;
564 unsigned long flags
= 0;
567 IRDA_DEBUG( 4, "%s()\n", __func__
);
569 IRDA_ASSERT( hashbin
!= NULL
, return NULL
;);
570 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
576 hashv
= hash( name
);
577 bin
= GET_HASHBIN( hashv
);
580 if ( hashbin
->hb_type
& HB_LOCK
) {
581 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
582 } /* Default is no-lock */
587 entry
= hashbin
->hb_queue
[ bin
];
593 if ( entry
->q_hash
== hashv
) {
598 if ( strcmp( entry
->q_name
, name
) == 0)
608 entry
= entry
->q_next
;
609 } while ( entry
!= hashbin
->hb_queue
[ bin
] );
613 * If entry was found, dequeue it
616 dequeue_general( (irda_queue_t
**) &hashbin
->hb_queue
[ bin
],
617 (irda_queue_t
*) entry
);
621 * Check if this item is the currently selected item, and in
622 * that case we must reset hb_current
624 if ( entry
== hashbin
->hb_current
)
625 hashbin
->hb_current
= NULL
;
629 if ( hashbin
->hb_type
& HB_LOCK
) {
630 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
631 } /* Default is no-lock */
641 EXPORT_SYMBOL(hashbin_remove
);
644 * Function hashbin_remove_this (hashbin, entry)
646 * Remove entry with the given name
648 * In some cases, the user of hashbin can't guarantee the unicity
649 * of either the hashv or name.
650 * In those cases, using the above function is guaranteed to cause troubles,
651 * so we use this one instead...
652 * And by the way, it's also faster, because we skip the search phase ;-)
654 void* hashbin_remove_this( hashbin_t
* hashbin
, irda_queue_t
* entry
)
656 unsigned long flags
= 0;
660 IRDA_DEBUG( 4, "%s()\n", __func__
);
662 IRDA_ASSERT( hashbin
!= NULL
, return NULL
;);
663 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
664 IRDA_ASSERT( entry
!= NULL
, return NULL
;);
667 if ( hashbin
->hb_type
& HB_LOCK
) {
668 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
669 } /* Default is no-lock */
671 /* Check if valid and not already removed... */
672 if((entry
->q_next
== NULL
) || (entry
->q_prev
== NULL
)) {
680 hashv
= entry
->q_hash
;
681 bin
= GET_HASHBIN( hashv
);
684 * Dequeue the entry...
686 dequeue_general( (irda_queue_t
**) &hashbin
->hb_queue
[ bin
],
687 (irda_queue_t
*) entry
);
689 entry
->q_next
= NULL
;
690 entry
->q_prev
= NULL
;
693 * Check if this item is the currently selected item, and in
694 * that case we must reset hb_current
696 if ( entry
== hashbin
->hb_current
)
697 hashbin
->hb_current
= NULL
;
700 if ( hashbin
->hb_type
& HB_LOCK
) {
701 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
702 } /* Default is no-lock */
706 EXPORT_SYMBOL(hashbin_remove_this
);
708 /*********************** HASHBIN ENUMERATION ***********************/
711 * Function hashbin_common_find (hashbin, hashv, name)
713 * Find item with the given hashv or name
716 void* hashbin_find( hashbin_t
* hashbin
, long hashv
, const char* name
)
721 IRDA_DEBUG( 4, "hashbin_find()\n");
723 IRDA_ASSERT( hashbin
!= NULL
, return NULL
;);
724 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
730 hashv
= hash( name
);
731 bin
= GET_HASHBIN( hashv
);
736 entry
= hashbin
->hb_queue
[ bin
];
742 if ( entry
->q_hash
== hashv
) {
747 if ( strcmp( entry
->q_name
, name
) == 0 ) {
754 entry
= entry
->q_next
;
755 } while ( entry
!= hashbin
->hb_queue
[ bin
] );
760 EXPORT_SYMBOL(hashbin_find
);
763 * Function hashbin_lock_find (hashbin, hashv, name)
765 * Find item with the given hashv or name
767 * Same, but with spinlock protection...
768 * I call it safe, but it's only safe with respect to the hashbin, not its
771 void* hashbin_lock_find( hashbin_t
* hashbin
, long hashv
, const char* name
)
773 unsigned long flags
= 0;
777 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
782 entry
= (irda_queue_t
* ) hashbin_find( hashbin
, hashv
, name
);
785 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
789 EXPORT_SYMBOL(hashbin_lock_find
);
792 * Function hashbin_find (hashbin, hashv, name, pnext)
794 * Find an item with the given hashv or name, and its successor
796 * This function allow to do concurrent enumerations without the
797 * need to lock over the whole session, because the caller keep the
798 * context of the search. On the other hand, it might fail and return
799 * NULL if the entry is removed. - Jean II
801 void* hashbin_find_next( hashbin_t
* hashbin
, long hashv
, const char* name
,
804 unsigned long flags
= 0;
808 spin_lock_irqsave(&hashbin
->hb_spinlock
, flags
);
811 * Search for current entry
812 * This allow to check if the current item is still in the
813 * hashbin or has been removed.
815 entry
= (irda_queue_t
* ) hashbin_find( hashbin
, hashv
, name
);
818 * Trick hashbin_get_next() to return what we want
821 hashbin
->hb_current
= entry
;
822 *pnext
= hashbin_get_next( hashbin
);
827 spin_unlock_irqrestore(&hashbin
->hb_spinlock
, flags
);
833 * Function hashbin_get_first (hashbin)
835 * Get a pointer to first element in hashbin, this function must be
836 * called before any calls to hashbin_get_next()!
839 irda_queue_t
*hashbin_get_first( hashbin_t
* hashbin
)
844 IRDA_ASSERT( hashbin
!= NULL
, return NULL
;);
845 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
847 if ( hashbin
== NULL
)
850 for ( i
= 0; i
< HASHBIN_SIZE
; i
++ ) {
851 entry
= hashbin
->hb_queue
[ i
];
853 hashbin
->hb_current
= entry
;
858 * Did not find any item in hashbin
862 EXPORT_SYMBOL(hashbin_get_first
);
865 * Function hashbin_get_next (hashbin)
867 * Get next item in hashbin. A series of hashbin_get_next() calls must
868 * be started by a call to hashbin_get_first(). The function returns
869 * NULL when all items have been traversed
871 * The context of the search is stored within the hashbin, so you must
872 * protect yourself from concurrent enumerations. - Jean II
874 irda_queue_t
*hashbin_get_next( hashbin_t
*hashbin
)
880 IRDA_ASSERT( hashbin
!= NULL
, return NULL
;);
881 IRDA_ASSERT( hashbin
->magic
== HB_MAGIC
, return NULL
;);
883 if ( hashbin
->hb_current
== NULL
) {
884 IRDA_ASSERT( hashbin
->hb_current
!= NULL
, return NULL
;);
887 entry
= hashbin
->hb_current
->q_next
;
888 bin
= GET_HASHBIN( entry
->q_hash
);
891 * Make sure that we are not back at the beginning of the queue
894 if ( entry
!= hashbin
->hb_queue
[ bin
]) {
895 hashbin
->hb_current
= entry
;
901 * Check that this is not the last queue in hashbin
903 if ( bin
>= HASHBIN_SIZE
)
907 * Move to next queue in hashbin
910 for ( i
= bin
; i
< HASHBIN_SIZE
; i
++ ) {
911 entry
= hashbin
->hb_queue
[ i
];
913 hashbin
->hb_current
= entry
;
920 EXPORT_SYMBOL(hashbin_get_next
);
This page took 0.04852 seconds and 5 git commands to generate.