linux/net/irda/irqueue.c
<<
>>
Prefs
   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 */
 213static __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 */
 233static 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 */
 266static 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 */
 307static 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 */
 353hashbin_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}
 378EXPORT_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
 389static int hashbin_lock_depth = 0;
 390#endif
 391int 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}
 439EXPORT_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 */
 449void 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}
 491EXPORT_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 */
 502void *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                                 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 */
 562void* 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                                 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}
 642EXPORT_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 */
 655void* 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                         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;
 699out:
 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}
 707EXPORT_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 */
 717void* 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}
 761EXPORT_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 */
 772void* 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}
 790EXPORT_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 */
 802void* 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 */
 840irda_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}
 863EXPORT_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 */
 875irda_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}
 921EXPORT_SYMBOL(hashbin_get_next);
 922