]>
Commit | Line | Data |
---|---|---|
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 | /* | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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); |