• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  */
hash(const char * name)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  */
enqueue_first(irda_queue_t ** queue,irda_queue_t * element)233 static void enqueue_first(irda_queue_t **queue, irda_queue_t* element)
234 {
235 
236 	/*
237 	 * Check if queue is empty.
238 	 */
239 	if ( *queue == NULL ) {
240 		/*
241 		 * Queue is empty.  Insert one element into the queue.
242 		 */
243 		element->q_next = element->q_prev = *queue = element;
244 
245 	} else {
246 		/*
247 		 * Queue is not empty.  Insert element into front of queue.
248 		 */
249 		element->q_next          = (*queue);
250 		(*queue)->q_prev->q_next = element;
251 		element->q_prev          = (*queue)->q_prev;
252 		(*queue)->q_prev         = element;
253 		(*queue)                 = element;
254 	}
255 }
256 
257 
258 /*
259  * Function dequeue (queue)
260  *
261  *    Remove first entry in queue
262  *
263  */
dequeue_first(irda_queue_t ** queue)264 static irda_queue_t *dequeue_first(irda_queue_t **queue)
265 {
266 	irda_queue_t *ret;
267 
268 	pr_debug("dequeue_first()\n");
269 
270 	/*
271 	 * Set return value
272 	 */
273 	ret =  *queue;
274 
275 	if ( *queue == NULL ) {
276 		/*
277 		 * Queue was empty.
278 		 */
279 	} else if ( (*queue)->q_next == *queue ) {
280 		/*
281 		 *  Queue only contained a single element. It will now be
282 		 *  empty.
283 		 */
284 		*queue = NULL;
285 	} else {
286 		/*
287 		 * Queue contained several element.  Remove the first one.
288 		 */
289 		(*queue)->q_prev->q_next = (*queue)->q_next;
290 		(*queue)->q_next->q_prev = (*queue)->q_prev;
291 		*queue = (*queue)->q_next;
292 	}
293 
294 	/*
295 	 * Return the removed entry (or NULL of queue was empty).
296 	 */
297 	return ret;
298 }
299 
300 /*
301  * Function dequeue_general (queue, element)
302  *
303  *
304  */
dequeue_general(irda_queue_t ** queue,irda_queue_t * element)305 static irda_queue_t *dequeue_general(irda_queue_t **queue, irda_queue_t* element)
306 {
307 	irda_queue_t *ret;
308 
309 	pr_debug("dequeue_general()\n");
310 
311 	/*
312 	 * Set return value
313 	 */
314 	ret =  *queue;
315 
316 	if ( *queue == NULL ) {
317 		/*
318 		 * Queue was empty.
319 		 */
320 	} else if ( (*queue)->q_next == *queue ) {
321 		/*
322 		 *  Queue only contained a single element. It will now be
323 		 *  empty.
324 		 */
325 		*queue = NULL;
326 
327 	} else {
328 		/*
329 		 *  Remove specific element.
330 		 */
331 		element->q_prev->q_next = element->q_next;
332 		element->q_next->q_prev = element->q_prev;
333 		if ( (*queue) == element)
334 			(*queue) = element->q_next;
335 	}
336 
337 	/*
338 	 * Return the removed entry (or NULL of queue was empty).
339 	 */
340 	return ret;
341 }
342 
343 /************************ HASHBIN MANAGEMENT ************************/
344 
345 /*
346  * Function hashbin_create ( type, name )
347  *
348  *    Create hashbin!
349  *
350  */
hashbin_new(int type)351 hashbin_t *hashbin_new(int type)
352 {
353 	hashbin_t* hashbin;
354 
355 	/*
356 	 * Allocate new hashbin
357 	 */
358 	hashbin = kzalloc(sizeof(*hashbin), GFP_ATOMIC);
359 	if (!hashbin)
360 		return NULL;
361 
362 	/*
363 	 * Initialize structure
364 	 */
365 	hashbin->hb_type = type;
366 	hashbin->magic = HB_MAGIC;
367 	//hashbin->hb_current = NULL;
368 
369 	/* Make sure all spinlock's are unlocked */
370 	if ( hashbin->hb_type & HB_LOCK ) {
371 		spin_lock_init(&hashbin->hb_spinlock);
372 	}
373 
374 	return hashbin;
375 }
376 EXPORT_SYMBOL(hashbin_new);
377 
378 
379 /*
380  * Function hashbin_delete (hashbin, free_func)
381  *
382  *    Destroy hashbin, the free_func can be a user supplied special routine
383  *    for deallocating this structure if it's complex. If not the user can
384  *    just supply kfree, which should take care of the job.
385  */
hashbin_delete(hashbin_t * hashbin,FREE_FUNC free_func)386 int hashbin_delete( hashbin_t* hashbin, FREE_FUNC free_func)
387 {
388 	irda_queue_t* queue;
389 	unsigned long flags = 0;
390 	int i;
391 
392 	IRDA_ASSERT(hashbin != NULL, return -1;);
393 	IRDA_ASSERT(hashbin->magic == HB_MAGIC, return -1;);
394 
395 	/* Synchronize */
396 	if (hashbin->hb_type & HB_LOCK)
397 		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
398 
399 	/*
400 	 *  Free the entries in the hashbin, TODO: use hashbin_clear when
401 	 *  it has been shown to work
402 	 */
403 	for (i = 0; i < HASHBIN_SIZE; i ++ ) {
404 		while (1) {
405 			queue = dequeue_first((irda_queue_t**) &hashbin->hb_queue[i]);
406 
407 			if (!queue)
408 				break;
409 
410 			if (free_func) {
411 				if (hashbin->hb_type & HB_LOCK)
412 					spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
413 				free_func(queue);
414 				if (hashbin->hb_type & HB_LOCK)
415 					spin_lock_irqsave(&hashbin->hb_spinlock, flags);
416 			}
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 
428 	/*
429 	 *  Free the hashbin structure
430 	 */
431 	kfree(hashbin);
432 
433 	return 0;
434 }
435 EXPORT_SYMBOL(hashbin_delete);
436 
437 /********************* HASHBIN LIST OPERATIONS *********************/
438 
439 /*
440  * Function hashbin_insert (hashbin, entry, name)
441  *
442  *    Insert an entry into the hashbin
443  *
444  */
hashbin_insert(hashbin_t * hashbin,irda_queue_t * entry,long hashv,const char * name)445 void hashbin_insert(hashbin_t* hashbin, irda_queue_t* entry, long hashv,
446 		    const char* name)
447 {
448 	unsigned long flags = 0;
449 	int bin;
450 
451 	IRDA_ASSERT( hashbin != NULL, return;);
452 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return;);
453 
454 	/*
455 	 * Locate hashbin
456 	 */
457 	if ( name )
458 		hashv = hash( name );
459 	bin = GET_HASHBIN( hashv );
460 
461 	/* Synchronize */
462 	if ( hashbin->hb_type & HB_LOCK ) {
463 		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
464 	} /* Default is no-lock  */
465 
466 	/*
467 	 * Store name and key
468 	 */
469 	entry->q_hash = hashv;
470 	if ( name )
471 		strlcpy( entry->q_name, name, sizeof(entry->q_name));
472 
473 	/*
474 	 * Insert new entry first
475 	 */
476 	enqueue_first( (irda_queue_t**) &hashbin->hb_queue[ bin ],
477 		       entry);
478 	hashbin->hb_size++;
479 
480 	/* Release lock */
481 	if ( hashbin->hb_type & HB_LOCK ) {
482 		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
483 	} /* Default is no-lock  */
484 }
485 EXPORT_SYMBOL(hashbin_insert);
486 
487 /*
488  *  Function hashbin_remove_first (hashbin)
489  *
490  *    Remove first entry of the hashbin
491  *
492  * Note : this function no longer use hashbin_remove(), but does things
493  * similar to hashbin_remove_this(), so can be considered safe.
494  * Jean II
495  */
hashbin_remove_first(hashbin_t * hashbin)496 void *hashbin_remove_first( hashbin_t *hashbin)
497 {
498 	unsigned long flags = 0;
499 	irda_queue_t *entry = NULL;
500 
501 	/* Synchronize */
502 	if ( hashbin->hb_type & HB_LOCK ) {
503 		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
504 	} /* Default is no-lock  */
505 
506 	entry = hashbin_get_first( hashbin);
507 	if ( entry != NULL) {
508 		int	bin;
509 		long	hashv;
510 		/*
511 		 * Locate hashbin
512 		 */
513 		hashv = entry->q_hash;
514 		bin = GET_HASHBIN( hashv );
515 
516 		/*
517 		 * Dequeue the entry...
518 		 */
519 		dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
520 				 entry);
521 		hashbin->hb_size--;
522 		entry->q_next = NULL;
523 		entry->q_prev = NULL;
524 
525 		/*
526 		 *  Check if this item is the currently selected item, and in
527 		 *  that case we must reset hb_current
528 		 */
529 		if ( entry == hashbin->hb_current)
530 			hashbin->hb_current = NULL;
531 	}
532 
533 	/* Release lock */
534 	if ( hashbin->hb_type & HB_LOCK ) {
535 		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
536 	} /* Default is no-lock  */
537 
538 	return entry;
539 }
540 
541 
542 /*
543  *  Function hashbin_remove (hashbin, hashv, name)
544  *
545  *    Remove entry with the given name
546  *
547  *  The use of this function is highly discouraged, because the whole
548  *  concept behind hashbin_remove() is broken. In many cases, it's not
549  *  possible to guarantee the unicity of the index (either hashv or name),
550  *  leading to removing the WRONG entry.
551  *  The only simple safe use is :
552  *		hashbin_remove(hasbin, (int) self, NULL);
553  *  In other case, you must think hard to guarantee unicity of the index.
554  *  Jean II
555  */
hashbin_remove(hashbin_t * hashbin,long hashv,const char * name)556 void* hashbin_remove( hashbin_t* hashbin, long hashv, const char* name)
557 {
558 	int bin, found = FALSE;
559 	unsigned long flags = 0;
560 	irda_queue_t* entry;
561 
562 	IRDA_ASSERT( hashbin != NULL, return NULL;);
563 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
564 
565 	/*
566 	 * Locate hashbin
567 	 */
568 	if ( name )
569 		hashv = hash( name );
570 	bin = GET_HASHBIN( hashv );
571 
572 	/* Synchronize */
573 	if ( hashbin->hb_type & HB_LOCK ) {
574 		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
575 	} /* Default is no-lock  */
576 
577 	/*
578 	 * Search for entry
579 	 */
580 	entry = hashbin->hb_queue[ bin ];
581 	if ( entry ) {
582 		do {
583 			/*
584 			 * Check for key
585 			 */
586 			if ( entry->q_hash == hashv ) {
587 				/*
588 				 * Name compare too?
589 				 */
590 				if ( name ) {
591 					if ( strcmp( entry->q_name, name) == 0)
592 					{
593 						found = TRUE;
594 						break;
595 					}
596 				} else {
597 					found = TRUE;
598 					break;
599 				}
600 			}
601 			entry = entry->q_next;
602 		} while ( entry != hashbin->hb_queue[ bin ] );
603 	}
604 
605 	/*
606 	 * If entry was found, dequeue it
607 	 */
608 	if ( found ) {
609 		dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
610 				 entry);
611 		hashbin->hb_size--;
612 
613 		/*
614 		 *  Check if this item is the currently selected item, and in
615 		 *  that case we must reset hb_current
616 		 */
617 		if ( entry == hashbin->hb_current)
618 			hashbin->hb_current = NULL;
619 	}
620 
621 	/* Release lock */
622 	if ( hashbin->hb_type & HB_LOCK ) {
623 		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
624 	} /* Default is no-lock  */
625 
626 
627 	/* Return */
628 	if ( found )
629 		return entry;
630 	else
631 		return NULL;
632 
633 }
634 EXPORT_SYMBOL(hashbin_remove);
635 
636 /*
637  *  Function hashbin_remove_this (hashbin, entry)
638  *
639  *    Remove entry with the given name
640  *
641  * In some cases, the user of hashbin can't guarantee the unicity
642  * of either the hashv or name.
643  * In those cases, using the above function is guaranteed to cause troubles,
644  * so we use this one instead...
645  * And by the way, it's also faster, because we skip the search phase ;-)
646  */
hashbin_remove_this(hashbin_t * hashbin,irda_queue_t * entry)647 void* hashbin_remove_this( hashbin_t* hashbin, irda_queue_t* entry)
648 {
649 	unsigned long flags = 0;
650 	int	bin;
651 	long	hashv;
652 
653 	IRDA_ASSERT( hashbin != NULL, return NULL;);
654 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
655 	IRDA_ASSERT( entry != NULL, return NULL;);
656 
657 	/* Synchronize */
658 	if ( hashbin->hb_type & HB_LOCK ) {
659 		spin_lock_irqsave(&hashbin->hb_spinlock, flags);
660 	} /* Default is no-lock  */
661 
662 	/* Check if valid and not already removed... */
663 	if((entry->q_next == NULL) || (entry->q_prev == NULL)) {
664 		entry = NULL;
665 		goto out;
666 	}
667 
668 	/*
669 	 * Locate hashbin
670 	 */
671 	hashv = entry->q_hash;
672 	bin = GET_HASHBIN( hashv );
673 
674 	/*
675 	 * Dequeue the entry...
676 	 */
677 	dequeue_general( (irda_queue_t**) &hashbin->hb_queue[ bin ],
678 			 entry);
679 	hashbin->hb_size--;
680 	entry->q_next = NULL;
681 	entry->q_prev = NULL;
682 
683 	/*
684 	 *  Check if this item is the currently selected item, and in
685 	 *  that case we must reset hb_current
686 	 */
687 	if ( entry == hashbin->hb_current)
688 		hashbin->hb_current = NULL;
689 out:
690 	/* Release lock */
691 	if ( hashbin->hb_type & HB_LOCK ) {
692 		spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
693 	} /* Default is no-lock  */
694 
695 	return entry;
696 }
697 EXPORT_SYMBOL(hashbin_remove_this);
698 
699 /*********************** HASHBIN ENUMERATION ***********************/
700 
701 /*
702  * Function hashbin_common_find (hashbin, hashv, name)
703  *
704  *    Find item with the given hashv or name
705  *
706  */
hashbin_find(hashbin_t * hashbin,long hashv,const char * name)707 void* hashbin_find( hashbin_t* hashbin, long hashv, const char* name )
708 {
709 	int bin;
710 	irda_queue_t* entry;
711 
712 	pr_debug("hashbin_find()\n");
713 
714 	IRDA_ASSERT( hashbin != NULL, return NULL;);
715 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
716 
717 	/*
718 	 * Locate hashbin
719 	 */
720 	if ( name )
721 		hashv = hash( name );
722 	bin = GET_HASHBIN( hashv );
723 
724 	/*
725 	 * Search for entry
726 	 */
727 	entry = hashbin->hb_queue[ bin];
728 	if ( entry ) {
729 		do {
730 			/*
731 			 * Check for key
732 			 */
733 			if ( entry->q_hash == hashv ) {
734 				/*
735 				 * Name compare too?
736 				 */
737 				if ( name ) {
738 					if ( strcmp( entry->q_name, name ) == 0 ) {
739 						return entry;
740 					}
741 				} else {
742 					return entry;
743 				}
744 			}
745 			entry = entry->q_next;
746 		} while ( entry != hashbin->hb_queue[ bin ] );
747 	}
748 
749 	return NULL;
750 }
751 EXPORT_SYMBOL(hashbin_find);
752 
753 /*
754  * Function hashbin_lock_find (hashbin, hashv, name)
755  *
756  *    Find item with the given hashv or name
757  *
758  * Same, but with spinlock protection...
759  * I call it safe, but it's only safe with respect to the hashbin, not its
760  * content. - Jean II
761  */
hashbin_lock_find(hashbin_t * hashbin,long hashv,const char * name)762 void* hashbin_lock_find( hashbin_t* hashbin, long hashv, const char* name )
763 {
764 	unsigned long flags = 0;
765 	irda_queue_t* entry;
766 
767 	/* Synchronize */
768 	spin_lock_irqsave(&hashbin->hb_spinlock, flags);
769 
770 	/*
771 	 * Search for entry
772 	 */
773 	entry = hashbin_find(hashbin, hashv, name);
774 
775 	/* Release lock */
776 	spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
777 
778 	return entry;
779 }
780 EXPORT_SYMBOL(hashbin_lock_find);
781 
782 /*
783  * Function hashbin_find (hashbin, hashv, name, pnext)
784  *
785  *    Find an item with the given hashv or name, and its successor
786  *
787  * This function allow to do concurrent enumerations without the
788  * need to lock over the whole session, because the caller keep the
789  * context of the search. On the other hand, it might fail and return
790  * NULL if the entry is removed. - Jean II
791  */
hashbin_find_next(hashbin_t * hashbin,long hashv,const char * name,void ** pnext)792 void* hashbin_find_next( hashbin_t* hashbin, long hashv, const char* name,
793 			 void ** pnext)
794 {
795 	unsigned long flags = 0;
796 	irda_queue_t* entry;
797 
798 	/* Synchronize */
799 	spin_lock_irqsave(&hashbin->hb_spinlock, flags);
800 
801 	/*
802 	 * Search for current entry
803 	 * This allow to check if the current item is still in the
804 	 * hashbin or has been removed.
805 	 */
806 	entry = hashbin_find(hashbin, hashv, name);
807 
808 	/*
809 	 * Trick hashbin_get_next() to return what we want
810 	 */
811 	if(entry) {
812 		hashbin->hb_current = entry;
813 		*pnext = hashbin_get_next( hashbin );
814 	} else
815 		*pnext = NULL;
816 
817 	/* Release lock */
818 	spin_unlock_irqrestore(&hashbin->hb_spinlock, flags);
819 
820 	return entry;
821 }
822 
823 /*
824  * Function hashbin_get_first (hashbin)
825  *
826  *    Get a pointer to first element in hashbin, this function must be
827  *    called before any calls to hashbin_get_next()!
828  *
829  */
hashbin_get_first(hashbin_t * hashbin)830 irda_queue_t *hashbin_get_first( hashbin_t* hashbin)
831 {
832 	irda_queue_t *entry;
833 	int i;
834 
835 	IRDA_ASSERT( hashbin != NULL, return NULL;);
836 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
837 
838 	if ( hashbin == NULL)
839 		return NULL;
840 
841 	for ( i = 0; i < HASHBIN_SIZE; i ++ ) {
842 		entry = hashbin->hb_queue[ i];
843 		if ( entry) {
844 			hashbin->hb_current = entry;
845 			return entry;
846 		}
847 	}
848 	/*
849 	 *  Did not find any item in hashbin
850 	 */
851 	return NULL;
852 }
853 EXPORT_SYMBOL(hashbin_get_first);
854 
855 /*
856  * Function hashbin_get_next (hashbin)
857  *
858  *    Get next item in hashbin. A series of hashbin_get_next() calls must
859  *    be started by a call to hashbin_get_first(). The function returns
860  *    NULL when all items have been traversed
861  *
862  * The context of the search is stored within the hashbin, so you must
863  * protect yourself from concurrent enumerations. - Jean II
864  */
hashbin_get_next(hashbin_t * hashbin)865 irda_queue_t *hashbin_get_next( hashbin_t *hashbin)
866 {
867 	irda_queue_t* entry;
868 	int bin;
869 	int i;
870 
871 	IRDA_ASSERT( hashbin != NULL, return NULL;);
872 	IRDA_ASSERT( hashbin->magic == HB_MAGIC, return NULL;);
873 
874 	if ( hashbin->hb_current == NULL) {
875 		IRDA_ASSERT( hashbin->hb_current != NULL, return NULL;);
876 		return NULL;
877 	}
878 	entry = hashbin->hb_current->q_next;
879 	bin = GET_HASHBIN( entry->q_hash);
880 
881 	/*
882 	 *  Make sure that we are not back at the beginning of the queue
883 	 *  again
884 	 */
885 	if ( entry != hashbin->hb_queue[ bin ]) {
886 		hashbin->hb_current = entry;
887 
888 		return entry;
889 	}
890 
891 	/*
892 	 *  Check that this is not the last queue in hashbin
893 	 */
894 	if ( bin >= HASHBIN_SIZE)
895 		return NULL;
896 
897 	/*
898 	 *  Move to next queue in hashbin
899 	 */
900 	bin++;
901 	for ( i = bin; i < HASHBIN_SIZE; i++ ) {
902 		entry = hashbin->hb_queue[ i];
903 		if ( entry) {
904 			hashbin->hb_current = entry;
905 
906 			return entry;
907 		}
908 	}
909 	return NULL;
910 }
911 EXPORT_SYMBOL(hashbin_get_next);
912