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