← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to net/irda/irqueue.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
net/irda/irqueue.c
 
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
                                 (irda_queue_t*) 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
                                 (irda_queue_t*) 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
                         (irda_queue_t*) 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);