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