1/* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21/* 22 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26/* 27 * mod_hash: flexible hash table implementation. 28 * 29 * This is a reasonably fast, reasonably flexible hash table implementation 30 * which features pluggable hash algorithms to support storing arbitrary keys 31 * and values. It is designed to handle small (< 100,000 items) amounts of 32 * data. The hash uses chaining to resolve collisions, and does not feature a 33 * mechanism to grow the hash. Care must be taken to pick nchains to be large 34 * enough for the application at hand, or lots of time will be wasted searching 35 * hash chains. 36 * 37 * The client of the hash is required to supply a number of items to support 38 * the various hash functions: 39 * 40 * - Destructor functions for the key and value being hashed. 41 * A destructor is responsible for freeing an object when the hash 42 * table is no longer storing it. Since keys and values can be of 43 * arbitrary type, separate destructors for keys & values are used. 44 * These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no 45 * destructor is needed for either a key or value. 46 * 47 * - A hashing algorithm which returns a uint_t representing a hash index 48 * The number returned need _not_ be between 0 and nchains. The mod_hash 49 * code will take care of doing that. The second argument (after the 50 * key) to the hashing function is a void * that represents 51 * hash_alg_data-- this is provided so that the hashing algorithm can 52 * maintain some state across calls, or keep algorithm-specific 53 * constants associated with the hash table. 54 * 55 * A pointer-hashing and a string-hashing algorithm are supplied in 56 * this file. 57 * 58 * - A key comparator (a la qsort). 59 * This is used when searching the hash chain. The key comparator 60 * determines if two keys match. It should follow the return value 61 * semantics of strcmp. 62 * 63 * string and pointer comparators are supplied in this file. 64 * 65 * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good 66 * examples of how to create a customized hash table. 67 * 68 * Basic hash operations: 69 * 70 * mod_hash_create_strhash(name, nchains, dtor), 71 * create a hash using strings as keys. 72 * NOTE: This create a hash which automatically cleans up the string 73 * values it is given for keys. 74 * 75 * mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size): 76 * create a hash using pointers as keys. 77 * 78 * mod_hash_create_extended(name, nchains, kdtor, vdtor, 79 * hash_alg, hash_alg_data, 80 * keycmp, sleep) 81 * create a customized hash table. 82 * 83 * mod_hash_destroy_hash(hash): 84 * destroy the given hash table, calling the key and value destructors 85 * on each key-value pair stored in the hash. 86 * 87 * mod_hash_insert(hash, key, val): 88 * place a key, value pair into the given hash. 89 * duplicate keys are rejected. 90 * 91 * mod_hash_insert_reserve(hash, key, val, handle): 92 * place a key, value pair into the given hash, using handle to indicate 93 * the reserved storage for the pair. (no memory allocation is needed 94 * during a mod_hash_insert_reserve.) duplicate keys are rejected. 95 * 96 * mod_hash_reserve(hash, *handle): 97 * reserve storage for a key-value pair using the memory allocation 98 * policy of 'hash', returning the storage handle in 'handle'. 99 * 100 * mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value 101 * pair ignoring the memory allocation policy of 'hash' and always without 102 * sleep, returning the storage handle in 'handle'. 103 * 104 * mod_hash_remove(hash, key, *val): 105 * remove a key-value pair with key 'key' from 'hash', destroying the 106 * stored key, and returning the value in val. 107 * 108 * mod_hash_replace(hash, key, val) 109 * atomically remove an existing key-value pair from a hash, and replace 110 * the key and value with the ones supplied. The removed key and value 111 * (if any) are destroyed. 112 * 113 * mod_hash_destroy(hash, key): 114 * remove a key-value pair with key 'key' from 'hash', destroying both 115 * stored key and stored value. 116 * 117 * mod_hash_find(hash, key, val): 118 * find a value in the hash table corresponding to the given key. 119 * 120 * mod_hash_find_cb(hash, key, val, found_callback) 121 * find a value in the hash table corresponding to the given key. 122 * If a value is found, call specified callback passing key and val to it. 123 * The callback is called with the hash lock held. 124 * It is intended to be used in situations where the act of locating the 125 * data must also modify it - such as in reference counting schemes. 126 * 127 * mod_hash_walk(hash, callback(key, elem, arg), arg) 128 * walks all the elements in the hashtable and invokes the callback 129 * function with the key/value pair for each element. the hashtable 130 * is locked for readers so the callback function should not attempt 131 * to do any updates to the hashable. the callback function should 132 * return MH_WALK_CONTINUE to continue walking the hashtable or 133 * MH_WALK_TERMINATE to abort the walk of the hashtable. 134 * 135 * mod_hash_clear(hash): 136 * clears the given hash table of entries, calling the key and value 137 * destructors for every element in the hash. 138 */ 139 140#include <sys/zfs_context.h> 141#include <sys/bitmap.h> 142#include <sys/modhash_impl.h> 143#include <sys/sysmacros.h> 144 145/* 146 * MH_KEY_DESTROY() 147 * Invoke the key destructor. 148 */ 149#define MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key)) 150 151/* 152 * MH_VAL_DESTROY() 153 * Invoke the value destructor. 154 */ 155#define MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val)) 156 157/* 158 * MH_KEYCMP() 159 * Call the key comparator for the given hash keys. 160 */ 161#define MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2)) 162 163/* 164 * Cache for struct mod_hash_entry 165 */ 166kmem_cache_t *mh_e_cache = NULL; 167mod_hash_t *mh_head = NULL; 168kmutex_t mh_head_lock; 169 170/* 171 * mod_hash_null_keydtor() 172 * mod_hash_null_valdtor() 173 * no-op key and value destructors. 174 */ 175/*ARGSUSED*/ 176void 177mod_hash_null_keydtor(mod_hash_key_t key) 178{ 179} 180 181/*ARGSUSED*/ 182void 183mod_hash_null_valdtor(mod_hash_val_t val) 184{ 185} 186 187/* 188 * mod_hash_bystr() 189 * mod_hash_strkey_cmp() 190 * mod_hash_strkey_dtor() 191 * mod_hash_strval_dtor() 192 * Hash and key comparison routines for hashes with string keys. 193 * 194 * mod_hash_create_strhash() 195 * Create a hash using strings as keys 196 * 197 * The string hashing algorithm is from the "Dragon Book" -- 198 * "Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman 199 */ 200 201/*ARGSUSED*/ 202uint_t 203mod_hash_bystr(void *hash_data, mod_hash_key_t key) 204{ 205 uint_t hash = 0; 206 uint_t g; 207 char *p, *k = (char *)key; 208 209 ASSERT(k); 210 for (p = k; *p != '\0'; p++) { 211 hash = (hash << 4) + *p; 212 if ((g = (hash & 0xf0000000)) != 0) { 213 hash ^= (g >> 24); 214 hash ^= g; 215 } 216 } 217 return (hash); 218} 219 220int 221mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 222{ 223 return (strcmp((char *)key1, (char *)key2)); 224} 225 226void 227mod_hash_strkey_dtor(mod_hash_key_t key) 228{ 229 char *c = (char *)key; 230 kmem_free(c, strlen(c) + 1); 231} 232 233void 234mod_hash_strval_dtor(mod_hash_val_t val) 235{ 236 char *c = (char *)val; 237 kmem_free(c, strlen(c) + 1); 238} 239 240mod_hash_t * 241mod_hash_create_strhash_nodtr(char *name, size_t nchains, 242 void (*val_dtor)(mod_hash_val_t)) 243{ 244 return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, 245 val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP); 246} 247 248mod_hash_t * 249mod_hash_create_strhash(char *name, size_t nchains, 250 void (*val_dtor)(mod_hash_val_t)) 251{ 252 return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor, 253 val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP); 254} 255 256void 257mod_hash_destroy_strhash(mod_hash_t *strhash) 258{ 259 ASSERT(strhash); 260 mod_hash_destroy_hash(strhash); 261} 262 263 264/* 265 * mod_hash_byptr() 266 * mod_hash_ptrkey_cmp() 267 * Hash and key comparison routines for hashes with pointer keys. 268 * 269 * mod_hash_create_ptrhash() 270 * mod_hash_destroy_ptrhash() 271 * Create a hash that uses pointers as keys. This hash algorithm 272 * picks an appropriate set of middle bits in the address to hash on 273 * based on the size of the hash table and a hint about the size of 274 * the items pointed at. 275 */ 276uint_t 277mod_hash_byptr(void *hash_data, mod_hash_key_t key) 278{ 279 uintptr_t k = (uintptr_t)key; 280 k >>= (int)(uintptr_t)hash_data; 281 282 return ((uint_t)k); 283} 284 285int 286mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 287{ 288 uintptr_t k1 = (uintptr_t)key1; 289 uintptr_t k2 = (uintptr_t)key2; 290 if (k1 > k2) 291 return (-1); 292 else if (k1 < k2) 293 return (1); 294 else 295 return (0); 296} 297 298mod_hash_t * 299mod_hash_create_ptrhash(char *name, size_t nchains, 300 void (*val_dtor)(mod_hash_val_t), size_t key_elem_size) 301{ 302 size_t rshift; 303 304 /* 305 * We want to hash on the bits in the middle of the address word 306 * Bits far to the right in the word have little significance, and 307 * are likely to all look the same (for example, an array of 308 * 256-byte structures will have the bottom 8 bits of address 309 * words the same). So we want to right-shift each address to 310 * ignore the bottom bits. 311 * 312 * The high bits, which are also unused, will get taken out when 313 * mod_hash takes hashkey % nchains. 314 */ 315 rshift = highbit64(key_elem_size); 316 317 return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, 318 val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp, 319 KM_SLEEP); 320} 321 322void 323mod_hash_destroy_ptrhash(mod_hash_t *hash) 324{ 325 ASSERT(hash); 326 mod_hash_destroy_hash(hash); 327} 328 329/* 330 * mod_hash_byid() 331 * mod_hash_idkey_cmp() 332 * Hash and key comparison routines for hashes with 32-bit unsigned keys. 333 * 334 * mod_hash_create_idhash() 335 * mod_hash_destroy_idhash() 336 * mod_hash_iddata_gen() 337 * Create a hash that uses numeric keys. 338 * 339 * The hash algorithm is documented in "Introduction to Algorithms" 340 * (Cormen, Leiserson, Rivest); when the hash table is created, it 341 * attempts to find the next largest prime above the number of hash 342 * slots. The hash index is then this number times the key modulo 343 * the hash size, or (key * prime) % nchains. 344 */ 345uint_t 346mod_hash_byid(void *hash_data, mod_hash_key_t key) 347{ 348 uint_t kval = (uint_t)(uintptr_t)hash_data; 349 return ((uint_t)(uintptr_t)key * (uint_t)kval); 350} 351 352int 353mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2) 354{ 355 return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2); 356} 357 358/* 359 * Generate the next largest prime number greater than nchains; this value 360 * is intended to be later passed in to mod_hash_create_extended() as the 361 * hash_data. 362 */ 363uint_t 364mod_hash_iddata_gen(size_t nchains) 365{ 366 uint_t kval, i, prime; 367 368 /* 369 * Pick the first (odd) prime greater than nchains. Make sure kval is 370 * odd (so start with nchains +1 or +2 as appropriate). 371 */ 372 kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2; 373 374 for (;;) { 375 prime = 1; 376 for (i = 3; i * i <= kval; i += 2) { 377 if (kval % i == 0) 378 prime = 0; 379 } 380 if (prime == 1) 381 break; 382 kval += 2; 383 } 384 return (kval); 385} 386 387mod_hash_t * 388mod_hash_create_idhash(char *name, size_t nchains, 389 void (*val_dtor)(mod_hash_val_t)) 390{ 391 uint_t kval = mod_hash_iddata_gen(nchains); 392 393 return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor, 394 val_dtor, mod_hash_byid, (void *)(uintptr_t)kval, 395 mod_hash_idkey_cmp, KM_SLEEP)); 396} 397 398void 399mod_hash_destroy_idhash(mod_hash_t *hash) 400{ 401 ASSERT(hash); 402 mod_hash_destroy_hash(hash); 403} 404 405void 406mod_hash_fini(void) 407{ 408 mutex_destroy(&mh_head_lock); 409 410 if (mh_e_cache) { 411 kmem_cache_destroy(mh_e_cache); 412 mh_e_cache = NULL; 413 } 414} 415 416/* 417 * mod_hash_init() 418 * sets up globals, etc for mod_hash_* 419 */ 420void 421mod_hash_init(void) 422{ 423 ASSERT(mh_e_cache == NULL); 424 mh_e_cache = kmem_cache_create("mod_hash_entries", 425 sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL, 426 NULL, 0); 427 428 mutex_init(&mh_head_lock, NULL, MUTEX_DEFAULT, NULL); 429} 430 431/* 432 * mod_hash_create_extended() 433 * The full-blown hash creation function. 434 * 435 * notes: 436 * nchains - how many hash slots to create. More hash slots will 437 * result in shorter hash chains, but will consume 438 * slightly more memory up front. 439 * sleep - should be KM_SLEEP or KM_NOSLEEP, to indicate whether 440 * to sleep for memory, or fail in low-memory conditions. 441 * 442 * Fails only if KM_NOSLEEP was specified, and no memory was available. 443 */ 444mod_hash_t * 445mod_hash_create_extended( 446 char *hname, /* descriptive name for hash */ 447 size_t nchains, /* number of hash slots */ 448 void (*kdtor)(mod_hash_key_t), /* key destructor */ 449 void (*vdtor)(mod_hash_val_t), /* value destructor */ 450 uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */ 451 void *hash_alg_data, /* pass-thru arg for hash_alg */ 452 int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */ 453 int sleep) /* whether to sleep for mem */ 454{ 455 mod_hash_t *mod_hash; 456 size_t size; 457 ASSERT(hname && keycmp && hash_alg && vdtor && kdtor); 458 459 if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL) 460 return (NULL); 461 462 size = strlen(hname) + 1; 463 mod_hash->mh_name = kmem_alloc(size, sleep); 464 if (mod_hash->mh_name == NULL) { 465 kmem_free(mod_hash, MH_SIZE(nchains)); 466 return (NULL); 467 } 468 (void) strlcpy(mod_hash->mh_name, hname, size); 469 470 rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL); 471 mod_hash->mh_sleep = sleep; 472 mod_hash->mh_nchains = nchains; 473 mod_hash->mh_kdtor = kdtor; 474 mod_hash->mh_vdtor = vdtor; 475 mod_hash->mh_hashalg = hash_alg; 476 mod_hash->mh_hashalg_data = hash_alg_data; 477 mod_hash->mh_keycmp = keycmp; 478 479 /* 480 * Link the hash up on the list of hashes 481 */ 482 mutex_enter(&mh_head_lock); 483 mod_hash->mh_next = mh_head; 484 mh_head = mod_hash; 485 mutex_exit(&mh_head_lock); 486 487 return (mod_hash); 488} 489 490/* 491 * mod_hash_destroy_hash() 492 * destroy a hash table, destroying all of its stored keys and values 493 * as well. 494 */ 495void 496mod_hash_destroy_hash(mod_hash_t *hash) 497{ 498 mod_hash_t *mhp, *mhpp; 499 500 mutex_enter(&mh_head_lock); 501 /* 502 * Remove the hash from the hash list 503 */ 504 if (hash == mh_head) { /* removing 1st list elem */ 505 mh_head = mh_head->mh_next; 506 } else { 507 /* 508 * mhpp can start out NULL since we know the 1st elem isn't the 509 * droid we're looking for. 510 */ 511 mhpp = NULL; 512 for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) { 513 if (mhp == hash) { 514 mhpp->mh_next = mhp->mh_next; 515 break; 516 } 517 mhpp = mhp; 518 } 519 } 520 mutex_exit(&mh_head_lock); 521 522 /* 523 * Clean out keys and values. 524 */ 525 mod_hash_clear(hash); 526 527 rw_destroy(&hash->mh_contents); 528 kmem_free(hash->mh_name, strlen(hash->mh_name) + 1); 529 kmem_free(hash, MH_SIZE(hash->mh_nchains)); 530} 531 532/* 533 * i_mod_hash() 534 * Call the hashing algorithm for this hash table, with the given key. 535 */ 536uint_t 537i_mod_hash(mod_hash_t *hash, mod_hash_key_t key) 538{ 539 uint_t h; 540 /* 541 * Prevent div by 0 problems; 542 * Also a nice shortcut when using a hash as a list 543 */ 544 if (hash->mh_nchains == 1) 545 return (0); 546 547 h = (hash->mh_hashalg)(hash->mh_hashalg_data, key); 548 return (h % (hash->mh_nchains - 1)); 549} 550 551/* 552 * i_mod_hash_insert_nosync() 553 * mod_hash_insert() 554 * mod_hash_insert_reserve() 555 * insert 'val' into the hash table, using 'key' as its key. If 'key' is 556 * already a key in the hash, an error will be returned, and the key-val 557 * pair will not be inserted. i_mod_hash_insert_nosync() supports a simple 558 * handle abstraction, allowing hash entry allocation to be separated from 559 * the hash insertion. this abstraction allows simple use of the mod_hash 560 * structure in situations where mod_hash_insert() with a KM_SLEEP 561 * allocation policy would otherwise be unsafe. 562 */ 563int 564i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key, 565 mod_hash_val_t val, mod_hash_hndl_t handle) 566{ 567 uint_t hashidx; 568 struct mod_hash_entry *entry; 569 570 ASSERT(hash); 571 572 /* 573 * If we've not been given reserved storage, allocate storage directly, 574 * using the hash's allocation policy. 575 */ 576 if (handle == (mod_hash_hndl_t)0) { 577 entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep); 578 if (entry == NULL) { 579 hash->mh_stat.mhs_nomem++; 580 return (MH_ERR_NOMEM); 581 } 582 } else { 583 entry = (struct mod_hash_entry *)handle; 584 } 585 586 hashidx = i_mod_hash(hash, key); 587 entry->mhe_key = key; 588 entry->mhe_val = val; 589 entry->mhe_next = hash->mh_entries[hashidx]; 590 591 hash->mh_entries[hashidx] = entry; 592 hash->mh_stat.mhs_nelems++; 593 594 return (0); 595} 596 597int 598mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val) 599{ 600 int res; 601 mod_hash_val_t v; 602 603 rw_enter(&hash->mh_contents, RW_WRITER); 604 605 /* 606 * Disallow duplicate keys in the hash 607 */ 608 if (i_mod_hash_find_nosync(hash, key, &v) == 0) { 609 rw_exit(&hash->mh_contents); 610 hash->mh_stat.mhs_coll++; 611 return (MH_ERR_DUPLICATE); 612 } 613 614 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0); 615 rw_exit(&hash->mh_contents); 616 617 return (res); 618} 619 620int 621mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key, 622 mod_hash_val_t val, mod_hash_hndl_t handle) 623{ 624 int res; 625 mod_hash_val_t v; 626 627 rw_enter(&hash->mh_contents, RW_WRITER); 628 629 /* 630 * Disallow duplicate keys in the hash 631 */ 632 if (i_mod_hash_find_nosync(hash, key, &v) == 0) { 633 rw_exit(&hash->mh_contents); 634 hash->mh_stat.mhs_coll++; 635 return (MH_ERR_DUPLICATE); 636 } 637 res = i_mod_hash_insert_nosync(hash, key, val, handle); 638 rw_exit(&hash->mh_contents); 639 640 return (res); 641} 642 643/* 644 * mod_hash_reserve() 645 * mod_hash_reserve_nosleep() 646 * mod_hash_cancel() 647 * Make or cancel a mod_hash_entry_t reservation. Reservations are used in 648 * mod_hash_insert_reserve() above. 649 */ 650int 651mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep) 652{ 653 *handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep); 654 if (*handlep == NULL) { 655 hash->mh_stat.mhs_nomem++; 656 return (MH_ERR_NOMEM); 657 } 658 659 return (0); 660} 661 662int 663mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep) 664{ 665 *handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP); 666 if (*handlep == NULL) { 667 hash->mh_stat.mhs_nomem++; 668 return (MH_ERR_NOMEM); 669 } 670 671 return (0); 672 673} 674 675/*ARGSUSED*/ 676void 677mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep) 678{ 679 kmem_cache_free(mh_e_cache, *handlep); 680 *handlep = (mod_hash_hndl_t)0; 681} 682 683/* 684 * i_mod_hash_remove_nosync() 685 * mod_hash_remove() 686 * Remove an element from the hash table. 687 */ 688int 689i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key, 690 mod_hash_val_t *val) 691{ 692 int hashidx; 693 struct mod_hash_entry *e, *ep; 694 695 hashidx = i_mod_hash(hash, key); 696 ep = NULL; /* e's parent */ 697 698 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) { 699 if (MH_KEYCMP(hash, e->mhe_key, key) == 0) 700 break; 701 ep = e; 702 } 703 704 if (e == NULL) { /* not found */ 705 return (MH_ERR_NOTFOUND); 706 } 707 708 if (ep == NULL) /* special case 1st element in bucket */ 709 hash->mh_entries[hashidx] = e->mhe_next; 710 else 711 ep->mhe_next = e->mhe_next; 712 713 /* 714 * Clean up resources used by the node's key. 715 */ 716 MH_KEY_DESTROY(hash, e->mhe_key); 717 718 *val = e->mhe_val; 719 kmem_cache_free(mh_e_cache, e); 720 hash->mh_stat.mhs_nelems--; 721 722 return (0); 723} 724 725int 726mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val) 727{ 728 int res; 729 730 rw_enter(&hash->mh_contents, RW_WRITER); 731 res = i_mod_hash_remove_nosync(hash, key, val); 732 rw_exit(&hash->mh_contents); 733 734 return (res); 735} 736 737/* 738 * mod_hash_replace() 739 * atomically remove an existing key-value pair from a hash, and replace 740 * the key and value with the ones supplied. The removed key and value 741 * (if any) are destroyed. 742 */ 743int 744mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val) 745{ 746 int res; 747 mod_hash_val_t v; 748 749 rw_enter(&hash->mh_contents, RW_WRITER); 750 751 if (i_mod_hash_remove_nosync(hash, key, &v) == 0) { 752 /* 753 * mod_hash_remove() takes care of freeing up the key resources. 754 */ 755 MH_VAL_DESTROY(hash, v); 756 } 757 res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0); 758 759 rw_exit(&hash->mh_contents); 760 761 return (res); 762} 763 764/* 765 * mod_hash_destroy() 766 * Remove an element from the hash table matching 'key', and destroy it. 767 */ 768int 769mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key) 770{ 771 mod_hash_val_t val; 772 int rv; 773 774 rw_enter(&hash->mh_contents, RW_WRITER); 775 776 if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) { 777 /* 778 * mod_hash_remove() takes care of freeing up the key resources. 779 */ 780 MH_VAL_DESTROY(hash, val); 781 } 782 783 rw_exit(&hash->mh_contents); 784 return (rv); 785} 786 787/* 788 * i_mod_hash_find_nosync() 789 * mod_hash_find() 790 * Find a value in the hash table corresponding to the given key. 791 */ 792int 793i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key, 794 mod_hash_val_t *val) 795{ 796 uint_t hashidx; 797 struct mod_hash_entry *e; 798 799 hashidx = i_mod_hash(hash, key); 800 801 for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) { 802 if (MH_KEYCMP(hash, e->mhe_key, key) == 0) { 803 *val = e->mhe_val; 804 hash->mh_stat.mhs_hit++; 805 return (0); 806 } 807 } 808 hash->mh_stat.mhs_miss++; 809 return (MH_ERR_NOTFOUND); 810} 811 812int 813mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val) 814{ 815 int res; 816 817 rw_enter(&hash->mh_contents, RW_READER); 818 res = i_mod_hash_find_nosync(hash, key, val); 819 rw_exit(&hash->mh_contents); 820 821 return (res); 822} 823 824int 825mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val, 826 void (*find_cb)(mod_hash_key_t, mod_hash_val_t)) 827{ 828 int res; 829 830 rw_enter(&hash->mh_contents, RW_READER); 831 res = i_mod_hash_find_nosync(hash, key, val); 832 if (res == 0) { 833 find_cb(key, *val); 834 } 835 rw_exit(&hash->mh_contents); 836 837 return (res); 838} 839 840int 841mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val, 842 int (*find_cb)(mod_hash_key_t, mod_hash_val_t), int *cb_rval) 843{ 844 int res; 845 846 rw_enter(&hash->mh_contents, RW_READER); 847 res = i_mod_hash_find_nosync(hash, key, val); 848 if (res == 0) { 849 *cb_rval = find_cb(key, *val); 850 } 851 rw_exit(&hash->mh_contents); 852 853 return (res); 854} 855 856void 857i_mod_hash_walk_nosync(mod_hash_t *hash, 858 uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg) 859{ 860 struct mod_hash_entry *e; 861 uint_t hashidx; 862 int res = MH_WALK_CONTINUE; 863 864 for (hashidx = 0; 865 (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE); 866 hashidx++) { 867 e = hash->mh_entries[hashidx]; 868 while ((e != NULL) && (res == MH_WALK_CONTINUE)) { 869 res = callback(e->mhe_key, e->mhe_val, arg); 870 e = e->mhe_next; 871 } 872 } 873} 874 875/* 876 * mod_hash_walk() 877 * Walks all the elements in the hashtable and invokes the callback 878 * function with the key/value pair for each element. The hashtable 879 * is locked for readers so the callback function should not attempt 880 * to do any updates to the hashable. The callback function should 881 * return MH_WALK_CONTINUE to continue walking the hashtable or 882 * MH_WALK_TERMINATE to abort the walk of the hashtable. 883 */ 884void 885mod_hash_walk(mod_hash_t *hash, 886 uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg) 887{ 888 rw_enter(&hash->mh_contents, RW_READER); 889 i_mod_hash_walk_nosync(hash, callback, arg); 890 rw_exit(&hash->mh_contents); 891} 892 893 894/* 895 * i_mod_hash_clear_nosync() 896 * mod_hash_clear() 897 * Clears the given hash table by calling the destructor of every hash 898 * element and freeing up all mod_hash_entry's. 899 */ 900void 901i_mod_hash_clear_nosync(mod_hash_t *hash) 902{ 903 int i; 904 struct mod_hash_entry *e, *old_e; 905 906 for (i = 0; i < hash->mh_nchains; i++) { 907 e = hash->mh_entries[i]; 908 while (e != NULL) { 909 MH_KEY_DESTROY(hash, e->mhe_key); 910 MH_VAL_DESTROY(hash, e->mhe_val); 911 old_e = e; 912 e = e->mhe_next; 913 kmem_cache_free(mh_e_cache, old_e); 914 } 915 hash->mh_entries[i] = NULL; 916 } 917 hash->mh_stat.mhs_nelems = 0; 918} 919 920void 921mod_hash_clear(mod_hash_t *hash) 922{ 923 ASSERT(hash); 924 rw_enter(&hash->mh_contents, RW_WRITER); 925 i_mod_hash_clear_nosync(hash); 926 rw_exit(&hash->mh_contents); 927} 928