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 */ 212static __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 */ 232static void enqueue_first(irda_queue_t **queue, irda_queue_t* element) 233{ 234 235 IRDA_DEBUG( 4, "%s()\n", __FUNCTION__); 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 */ 265static 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 */ 306static 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 */ 352hashbin_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} 377EXPORT_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 388static int hashbin_lock_depth = 0; 389#endif 390int 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} 438EXPORT_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 */ 448void 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", __FUNCTION__); 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} 490EXPORT_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 */ 501void *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 */ 561void* 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", __FUNCTION__); 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} 641EXPORT_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 */ 654void* 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", __FUNCTION__); 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; 698out: 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} 706EXPORT_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 */ 716void* 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} 760EXPORT_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 */ 771void* 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} 789EXPORT_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 */ 801void* 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 */ 839irda_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} 862EXPORT_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 */ 874irda_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} 920EXPORT_SYMBOL(hashbin_get_next); 921