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