xref: /titanic_41/usr/src/uts/common/os/modhash.c (revision da14cebe459d3275048785f25bd869cb09b5307f)
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 algrorithm 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/bitmap.h>
141 #include <sys/debug.h>
142 #include <sys/kmem.h>
143 #include <sys/sunddi.h>
144 
145 #include <sys/modhash_impl.h>
146 
147 /*
148  * MH_KEY_DESTROY()
149  * 	Invoke the key destructor.
150  */
151 #define	MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))
152 
153 /*
154  * MH_VAL_DESTROY()
155  * 	Invoke the value destructor.
156  */
157 #define	MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))
158 
159 /*
160  * MH_KEYCMP()
161  * 	Call the key comparator for the given hash keys.
162  */
163 #define	MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))
164 
165 /*
166  * Cache for struct mod_hash_entry
167  */
168 kmem_cache_t *mh_e_cache = NULL;
169 mod_hash_t *mh_head = NULL;
170 kmutex_t mh_head_lock;
171 
172 /*
173  * mod_hash_null_keydtor()
174  * mod_hash_null_valdtor()
175  * 	no-op key and value destructors.
176  */
177 /*ARGSUSED*/
178 void
mod_hash_null_keydtor(mod_hash_key_t key)179 mod_hash_null_keydtor(mod_hash_key_t key)
180 {
181 }
182 
183 /*ARGSUSED*/
184 void
mod_hash_null_valdtor(mod_hash_val_t val)185 mod_hash_null_valdtor(mod_hash_val_t val)
186 {
187 }
188 
189 /*
190  * mod_hash_bystr()
191  * mod_hash_strkey_cmp()
192  * mod_hash_strkey_dtor()
193  * mod_hash_strval_dtor()
194  *	Hash and key comparison routines for hashes with string keys.
195  *
196  * mod_hash_create_strhash()
197  * 	Create a hash using strings as keys
198  *
199  *	The string hashing algorithm is from the "Dragon Book" --
200  *	"Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman
201  */
202 
203 /*ARGSUSED*/
204 uint_t
mod_hash_bystr(void * hash_data,mod_hash_key_t key)205 mod_hash_bystr(void *hash_data, mod_hash_key_t key)
206 {
207 	uint_t hash = 0;
208 	uint_t g;
209 	char *p, *k = (char *)key;
210 
211 	ASSERT(k);
212 	for (p = k; *p != '\0'; p++) {
213 		hash = (hash << 4) + *p;
214 		if ((g = (hash & 0xf0000000)) != 0) {
215 			hash ^= (g >> 24);
216 			hash ^= g;
217 		}
218 	}
219 	return (hash);
220 }
221 
222 int
mod_hash_strkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)223 mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
224 {
225 	return (strcmp((char *)key1, (char *)key2));
226 }
227 
228 void
mod_hash_strkey_dtor(mod_hash_key_t key)229 mod_hash_strkey_dtor(mod_hash_key_t key)
230 {
231 	char *c = (char *)key;
232 	kmem_free(c, strlen(c) + 1);
233 }
234 
235 void
mod_hash_strval_dtor(mod_hash_val_t val)236 mod_hash_strval_dtor(mod_hash_val_t val)
237 {
238 	char *c = (char *)val;
239 	kmem_free(c, strlen(c) + 1);
240 }
241 
242 mod_hash_t *
mod_hash_create_strhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))243 mod_hash_create_strhash(char *name, size_t nchains,
244     void (*val_dtor)(mod_hash_val_t))
245 {
246 	return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor,
247 	    val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
248 }
249 
250 void
mod_hash_destroy_strhash(mod_hash_t * strhash)251 mod_hash_destroy_strhash(mod_hash_t *strhash)
252 {
253 	ASSERT(strhash);
254 	mod_hash_destroy_hash(strhash);
255 }
256 
257 
258 /*
259  * mod_hash_byptr()
260  * mod_hash_ptrkey_cmp()
261  *	Hash and key comparison routines for hashes with pointer keys.
262  *
263  * mod_hash_create_ptrhash()
264  * mod_hash_destroy_ptrhash()
265  * 	Create a hash that uses pointers as keys.  This hash algorithm
266  * 	picks an appropriate set of middle bits in the address to hash on
267  * 	based on the size of the hash table and a hint about the size of
268  * 	the items pointed at.
269  */
270 uint_t
mod_hash_byptr(void * hash_data,mod_hash_key_t key)271 mod_hash_byptr(void *hash_data, mod_hash_key_t key)
272 {
273 	uintptr_t k = (uintptr_t)key;
274 	k >>= (int)(uintptr_t)hash_data;
275 
276 	return ((uint_t)k);
277 }
278 
279 int
mod_hash_ptrkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)280 mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
281 {
282 	uintptr_t k1 = (uintptr_t)key1;
283 	uintptr_t k2 = (uintptr_t)key2;
284 	if (k1 > k2)
285 		return (-1);
286 	else if (k1 < k2)
287 		return (1);
288 	else
289 		return (0);
290 }
291 
292 mod_hash_t *
mod_hash_create_ptrhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t),size_t key_elem_size)293 mod_hash_create_ptrhash(char *name, size_t nchains,
294     void (*val_dtor)(mod_hash_val_t), size_t key_elem_size)
295 {
296 	size_t rshift;
297 
298 	/*
299 	 * We want to hash on the bits in the middle of the address word
300 	 * Bits far to the right in the word have little significance, and
301 	 * are likely to all look the same (for example, an array of
302 	 * 256-byte structures will have the bottom 8 bits of address
303 	 * words the same).  So we want to right-shift each address to
304 	 * ignore the bottom bits.
305 	 *
306 	 * The high bits, which are also unused, will get taken out when
307 	 * mod_hash takes hashkey % nchains.
308 	 */
309 	rshift = highbit(key_elem_size);
310 
311 	return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
312 	    val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp,
313 	    KM_SLEEP);
314 }
315 
316 void
mod_hash_destroy_ptrhash(mod_hash_t * hash)317 mod_hash_destroy_ptrhash(mod_hash_t *hash)
318 {
319 	ASSERT(hash);
320 	mod_hash_destroy_hash(hash);
321 }
322 
323 /*
324  * mod_hash_byid()
325  * mod_hash_idkey_cmp()
326  *	Hash and key comparison routines for hashes with 32-bit unsigned keys.
327  *
328  * mod_hash_create_idhash()
329  * mod_hash_destroy_idhash()
330  * mod_hash_iddata_gen()
331  * 	Create a hash that uses numeric keys.
332  *
333  *	The hash algorithm is documented in "Introduction to Algorithms"
334  *	(Cormen, Leiserson, Rivest);  when the hash table is created, it
335  *	attempts to find the next largest prime above the number of hash
336  *	slots.  The hash index is then this number times the key modulo
337  *	the hash size, or (key * prime) % nchains.
338  */
339 uint_t
mod_hash_byid(void * hash_data,mod_hash_key_t key)340 mod_hash_byid(void *hash_data, mod_hash_key_t key)
341 {
342 	uint_t kval = (uint_t)(uintptr_t)hash_data;
343 	return ((uint_t)(uintptr_t)key * (uint_t)kval);
344 }
345 
346 int
mod_hash_idkey_cmp(mod_hash_key_t key1,mod_hash_key_t key2)347 mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
348 {
349 	return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2);
350 }
351 
352 /*
353  * Generate the next largest prime number greater than nchains; this value
354  * is intended to be later passed in to mod_hash_create_extended() as the
355  * hash_data.
356  */
357 uint_t
mod_hash_iddata_gen(size_t nchains)358 mod_hash_iddata_gen(size_t nchains)
359 {
360 	uint_t kval, i, prime;
361 
362 	/*
363 	 * Pick the first (odd) prime greater than nchains.  Make sure kval is
364 	 * odd (so start with nchains +1 or +2 as appropriate).
365 	 */
366 	kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2;
367 
368 	for (;;) {
369 		prime = 1;
370 		for (i = 3; i * i <= kval; i += 2) {
371 			if (kval % i == 0)
372 				prime = 0;
373 		}
374 		if (prime == 1)
375 			break;
376 		kval += 2;
377 	}
378 	return (kval);
379 }
380 
381 mod_hash_t *
mod_hash_create_idhash(char * name,size_t nchains,void (* val_dtor)(mod_hash_val_t))382 mod_hash_create_idhash(char *name, size_t nchains,
383     void (*val_dtor)(mod_hash_val_t))
384 {
385 	uint_t kval = mod_hash_iddata_gen(nchains);
386 
387 	return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
388 	    val_dtor, mod_hash_byid, (void *)(uintptr_t)kval,
389 	    mod_hash_idkey_cmp, KM_SLEEP));
390 }
391 
392 void
mod_hash_destroy_idhash(mod_hash_t * hash)393 mod_hash_destroy_idhash(mod_hash_t *hash)
394 {
395 	ASSERT(hash);
396 	mod_hash_destroy_hash(hash);
397 }
398 
399 /*
400  * mod_hash_init()
401  * 	sets up globals, etc for mod_hash_*
402  */
403 void
mod_hash_init(void)404 mod_hash_init(void)
405 {
406 	ASSERT(mh_e_cache == NULL);
407 	mh_e_cache = kmem_cache_create("mod_hash_entries",
408 	    sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL,
409 	    NULL, 0);
410 }
411 
412 /*
413  * mod_hash_create_extended()
414  * 	The full-blown hash creation function.
415  *
416  * notes:
417  * 	nchains		- how many hash slots to create.  More hash slots will
418  *			  result in shorter hash chains, but will consume
419  *			  slightly more memory up front.
420  *	sleep		- should be KM_SLEEP or KM_NOSLEEP, to indicate whether
421  *			  to sleep for memory, or fail in low-memory conditions.
422  *
423  * 	Fails only if KM_NOSLEEP was specified, and no memory was available.
424  */
425 mod_hash_t *
mod_hash_create_extended(char * hname,size_t nchains,void (* kdtor)(mod_hash_key_t),void (* vdtor)(mod_hash_val_t),uint_t (* hash_alg)(void *,mod_hash_key_t),void * hash_alg_data,int (* keycmp)(mod_hash_key_t,mod_hash_key_t),int sleep)426 mod_hash_create_extended(
427     char *hname,			/* descriptive name for hash */
428     size_t nchains,			/* number of hash slots */
429     void (*kdtor)(mod_hash_key_t),	/* key destructor */
430     void (*vdtor)(mod_hash_val_t),	/* value destructor */
431     uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
432     void *hash_alg_data,		/* pass-thru arg for hash_alg */
433     int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */
434     int sleep)				/* whether to sleep for mem */
435 {
436 	mod_hash_t *mod_hash;
437 	ASSERT(hname && keycmp && hash_alg && vdtor && kdtor);
438 
439 	if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL)
440 		return (NULL);
441 
442 	mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep);
443 	if (mod_hash->mh_name == NULL) {
444 		kmem_free(mod_hash, MH_SIZE(nchains));
445 		return (NULL);
446 	}
447 	(void) strcpy(mod_hash->mh_name, hname);
448 
449 	mod_hash->mh_sleep = sleep;
450 	mod_hash->mh_nchains = nchains;
451 	mod_hash->mh_kdtor = kdtor;
452 	mod_hash->mh_vdtor = vdtor;
453 	mod_hash->mh_hashalg = hash_alg;
454 	mod_hash->mh_hashalg_data = hash_alg_data;
455 	mod_hash->mh_keycmp = keycmp;
456 
457 	/*
458 	 * Link the hash up on the list of hashes
459 	 */
460 	mutex_enter(&mh_head_lock);
461 	mod_hash->mh_next = mh_head;
462 	mh_head = mod_hash;
463 	mutex_exit(&mh_head_lock);
464 
465 	return (mod_hash);
466 }
467 
468 /*
469  * mod_hash_destroy_hash()
470  * 	destroy a hash table, destroying all of its stored keys and values
471  * 	as well.
472  */
473 void
mod_hash_destroy_hash(mod_hash_t * hash)474 mod_hash_destroy_hash(mod_hash_t *hash)
475 {
476 	mod_hash_t *mhp, *mhpp;
477 
478 	mutex_enter(&mh_head_lock);
479 	/*
480 	 * Remove the hash from the hash list
481 	 */
482 	if (hash == mh_head) {		/* removing 1st list elem */
483 		mh_head = mh_head->mh_next;
484 	} else {
485 		/*
486 		 * mhpp can start out NULL since we know the 1st elem isn't the
487 		 * droid we're looking for.
488 		 */
489 		mhpp = NULL;
490 		for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
491 			if (mhp == hash) {
492 				mhpp->mh_next = mhp->mh_next;
493 				break;
494 			}
495 			mhpp = mhp;
496 		}
497 	}
498 	mutex_exit(&mh_head_lock);
499 
500 	/*
501 	 * Clean out keys and values.
502 	 */
503 	mod_hash_clear(hash);
504 
505 	kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
506 	kmem_free(hash, MH_SIZE(hash->mh_nchains));
507 }
508 
509 /*
510  * i_mod_hash()
511  * 	Call the hashing algorithm for this hash table, with the given key.
512  */
513 uint_t
i_mod_hash(mod_hash_t * hash,mod_hash_key_t key)514 i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
515 {
516 	uint_t h;
517 	/*
518 	 * Prevent div by 0 problems;
519 	 * Also a nice shortcut when using a hash as a list
520 	 */
521 	if (hash->mh_nchains == 1)
522 		return (0);
523 
524 	h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
525 	return (h % (hash->mh_nchains - 1));
526 }
527 
528 /*
529  * i_mod_hash_insert_nosync()
530  * mod_hash_insert()
531  * mod_hash_insert_reserve()
532  * 	insert 'val' into the hash table, using 'key' as its key.  If 'key' is
533  * 	already a key in the hash, an error will be returned, and the key-val
534  * 	pair will not be inserted.  i_mod_hash_insert_nosync() supports a simple
535  * 	handle abstraction, allowing hash entry allocation to be separated from
536  * 	the hash insertion.  this abstraction allows simple use of the mod_hash
537  * 	structure in situations where mod_hash_insert() with a KM_SLEEP
538  * 	allocation policy would otherwise be unsafe.
539  */
540 int
i_mod_hash_insert_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val,mod_hash_hndl_t handle)541 i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key,
542     mod_hash_val_t val, mod_hash_hndl_t handle)
543 {
544 	uint_t hashidx;
545 	struct mod_hash_entry *entry;
546 
547 	ASSERT(hash);
548 
549 	/*
550 	 * If we've not been given reserved storage, allocate storage directly,
551 	 * using the hash's allocation policy.
552 	 */
553 	if (handle == (mod_hash_hndl_t)0) {
554 		entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
555 		if (entry == NULL) {
556 			hash->mh_stat.mhs_nomem++;
557 			return (MH_ERR_NOMEM);
558 		}
559 	} else {
560 		entry = (struct mod_hash_entry *)handle;
561 	}
562 
563 	hashidx = i_mod_hash(hash, key);
564 	entry->mhe_key = key;
565 	entry->mhe_val = val;
566 	entry->mhe_next = hash->mh_entries[hashidx];
567 
568 	hash->mh_entries[hashidx] = entry;
569 	hash->mh_stat.mhs_nelems++;
570 
571 	return (0);
572 }
573 
574 int
mod_hash_insert(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)575 mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
576 {
577 	int res;
578 	mod_hash_val_t v;
579 
580 	rw_enter(&hash->mh_contents, RW_WRITER);
581 
582 	/*
583 	 * Disallow duplicate keys in the hash
584 	 */
585 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
586 		rw_exit(&hash->mh_contents);
587 		hash->mh_stat.mhs_coll++;
588 		return (MH_ERR_DUPLICATE);
589 	}
590 
591 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
592 	rw_exit(&hash->mh_contents);
593 
594 	return (res);
595 }
596 
597 int
mod_hash_insert_reserve(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val,mod_hash_hndl_t handle)598 mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
599     mod_hash_val_t val, mod_hash_hndl_t handle)
600 {
601 	int res;
602 	mod_hash_val_t v;
603 
604 	rw_enter(&hash->mh_contents, RW_WRITER);
605 
606 	/*
607 	 * Disallow duplicate keys in the hash
608 	 */
609 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
610 		rw_exit(&hash->mh_contents);
611 		hash->mh_stat.mhs_coll++;
612 		return (MH_ERR_DUPLICATE);
613 	}
614 	res = i_mod_hash_insert_nosync(hash, key, val, handle);
615 	rw_exit(&hash->mh_contents);
616 
617 	return (res);
618 }
619 
620 /*
621  * mod_hash_reserve()
622  * mod_hash_reserve_nosleep()
623  * mod_hash_cancel()
624  *   Make or cancel a mod_hash_entry_t reservation.  Reservations are used in
625  *   mod_hash_insert_reserve() above.
626  */
627 int
mod_hash_reserve(mod_hash_t * hash,mod_hash_hndl_t * handlep)628 mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
629 {
630 	*handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
631 	if (*handlep == NULL) {
632 		hash->mh_stat.mhs_nomem++;
633 		return (MH_ERR_NOMEM);
634 	}
635 
636 	return (0);
637 }
638 
639 int
mod_hash_reserve_nosleep(mod_hash_t * hash,mod_hash_hndl_t * handlep)640 mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
641 {
642 	*handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
643 	if (*handlep == NULL) {
644 		hash->mh_stat.mhs_nomem++;
645 		return (MH_ERR_NOMEM);
646 	}
647 
648 	return (0);
649 
650 }
651 
652 /*ARGSUSED*/
653 void
mod_hash_cancel(mod_hash_t * hash,mod_hash_hndl_t * handlep)654 mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
655 {
656 	kmem_cache_free(mh_e_cache, *handlep);
657 	*handlep = (mod_hash_hndl_t)0;
658 }
659 
660 /*
661  * i_mod_hash_remove_nosync()
662  * mod_hash_remove()
663  * 	Remove an element from the hash table.
664  */
665 int
i_mod_hash_remove_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)666 i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
667     mod_hash_val_t *val)
668 {
669 	int hashidx;
670 	struct mod_hash_entry *e, *ep;
671 
672 	hashidx = i_mod_hash(hash, key);
673 	ep = NULL; /* e's parent */
674 
675 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
676 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
677 			break;
678 		ep = e;
679 	}
680 
681 	if (e == NULL) {	/* not found */
682 		return (MH_ERR_NOTFOUND);
683 	}
684 
685 	if (ep == NULL) 	/* special case 1st element in bucket */
686 		hash->mh_entries[hashidx] = e->mhe_next;
687 	else
688 		ep->mhe_next = e->mhe_next;
689 
690 	/*
691 	 * Clean up resources used by the node's key.
692 	 */
693 	MH_KEY_DESTROY(hash, e->mhe_key);
694 
695 	*val = e->mhe_val;
696 	kmem_cache_free(mh_e_cache, e);
697 	hash->mh_stat.mhs_nelems--;
698 
699 	return (0);
700 }
701 
702 int
mod_hash_remove(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)703 mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
704 {
705 	int res;
706 
707 	rw_enter(&hash->mh_contents, RW_WRITER);
708 	res = i_mod_hash_remove_nosync(hash, key, val);
709 	rw_exit(&hash->mh_contents);
710 
711 	return (res);
712 }
713 
714 /*
715  * mod_hash_replace()
716  * 	atomically remove an existing key-value pair from a hash, and replace
717  * 	the key and value with the ones supplied.  The removed key and value
718  * 	(if any) are destroyed.
719  */
720 int
mod_hash_replace(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t val)721 mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
722 {
723 	int res;
724 	mod_hash_val_t v;
725 
726 	rw_enter(&hash->mh_contents, RW_WRITER);
727 
728 	if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
729 		/*
730 		 * mod_hash_remove() takes care of freeing up the key resources.
731 		 */
732 		MH_VAL_DESTROY(hash, v);
733 	}
734 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
735 
736 	rw_exit(&hash->mh_contents);
737 
738 	return (res);
739 }
740 
741 /*
742  * mod_hash_destroy()
743  * 	Remove an element from the hash table matching 'key', and destroy it.
744  */
745 int
mod_hash_destroy(mod_hash_t * hash,mod_hash_key_t key)746 mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
747 {
748 	mod_hash_val_t val;
749 	int rv;
750 
751 	rw_enter(&hash->mh_contents, RW_WRITER);
752 
753 	if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
754 		/*
755 		 * mod_hash_remove() takes care of freeing up the key resources.
756 		 */
757 		MH_VAL_DESTROY(hash, val);
758 	}
759 
760 	rw_exit(&hash->mh_contents);
761 	return (rv);
762 }
763 
764 /*
765  * i_mod_hash_find_nosync()
766  * mod_hash_find()
767  * 	Find a value in the hash table corresponding to the given key.
768  */
769 int
i_mod_hash_find_nosync(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)770 i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
771     mod_hash_val_t *val)
772 {
773 	uint_t hashidx;
774 	struct mod_hash_entry *e;
775 
776 	hashidx = i_mod_hash(hash, key);
777 
778 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
779 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
780 			*val = e->mhe_val;
781 			hash->mh_stat.mhs_hit++;
782 			return (0);
783 		}
784 	}
785 	hash->mh_stat.mhs_miss++;
786 	return (MH_ERR_NOTFOUND);
787 }
788 
789 int
mod_hash_find(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val)790 mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
791 {
792 	int res;
793 
794 	rw_enter(&hash->mh_contents, RW_READER);
795 	res = i_mod_hash_find_nosync(hash, key, val);
796 	rw_exit(&hash->mh_contents);
797 
798 	return (res);
799 }
800 
801 int
mod_hash_find_cb(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val,void (* find_cb)(mod_hash_key_t,mod_hash_val_t))802 mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
803     void (*find_cb)(mod_hash_key_t, mod_hash_val_t))
804 {
805 	int res;
806 
807 	rw_enter(&hash->mh_contents, RW_READER);
808 	res = i_mod_hash_find_nosync(hash, key, val);
809 	if (res == 0) {
810 		find_cb(key, *val);
811 	}
812 	rw_exit(&hash->mh_contents);
813 
814 	return (res);
815 }
816 
817 int
mod_hash_find_cb_rval(mod_hash_t * hash,mod_hash_key_t key,mod_hash_val_t * val,int (* find_cb)(mod_hash_key_t,mod_hash_val_t),int * cb_rval)818 mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
819     int (*find_cb)(mod_hash_key_t, mod_hash_val_t), int *cb_rval)
820 {
821 	int res;
822 
823 	rw_enter(&hash->mh_contents, RW_READER);
824 	res = i_mod_hash_find_nosync(hash, key, val);
825 	if (res == 0) {
826 		*cb_rval = find_cb(key, *val);
827 	}
828 	rw_exit(&hash->mh_contents);
829 
830 	return (res);
831 }
832 
833 void
i_mod_hash_walk_nosync(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)834 i_mod_hash_walk_nosync(mod_hash_t *hash,
835     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
836 {
837 	struct mod_hash_entry	*e;
838 	uint_t			hashidx;
839 	int			res = MH_WALK_CONTINUE;
840 
841 	for (hashidx = 0;
842 	    (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
843 	    hashidx++) {
844 		e = hash->mh_entries[hashidx];
845 		while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
846 			res = callback(e->mhe_key, e->mhe_val, arg);
847 			e = e->mhe_next;
848 		}
849 	}
850 }
851 
852 /*
853  * mod_hash_walk()
854  * 	Walks all the elements in the hashtable and invokes the callback
855  * 	function with the key/value pair for each element.  The hashtable
856  * 	is locked for readers so the callback function should not attempt
857  * 	to do any updates to the hashable.  The callback function should
858  * 	return MH_WALK_CONTINUE to continue walking the hashtable or
859  * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
860  */
861 void
mod_hash_walk(mod_hash_t * hash,uint_t (* callback)(mod_hash_key_t,mod_hash_val_t *,void *),void * arg)862 mod_hash_walk(mod_hash_t *hash,
863     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
864 {
865 	rw_enter(&hash->mh_contents, RW_READER);
866 	i_mod_hash_walk_nosync(hash, callback, arg);
867 	rw_exit(&hash->mh_contents);
868 }
869 
870 
871 /*
872  * i_mod_hash_clear_nosync()
873  * mod_hash_clear()
874  *	Clears the given hash table by calling the destructor of every hash
875  *	element and freeing up all mod_hash_entry's.
876  */
877 void
i_mod_hash_clear_nosync(mod_hash_t * hash)878 i_mod_hash_clear_nosync(mod_hash_t *hash)
879 {
880 	int i;
881 	struct mod_hash_entry *e, *old_e;
882 
883 	for (i = 0; i < hash->mh_nchains; i++) {
884 		e = hash->mh_entries[i];
885 		while (e != NULL) {
886 			MH_KEY_DESTROY(hash, e->mhe_key);
887 			MH_VAL_DESTROY(hash, e->mhe_val);
888 			old_e = e;
889 			e = e->mhe_next;
890 			kmem_cache_free(mh_e_cache, old_e);
891 		}
892 		hash->mh_entries[i] = NULL;
893 	}
894 	hash->mh_stat.mhs_nelems = 0;
895 }
896 
897 void
mod_hash_clear(mod_hash_t * hash)898 mod_hash_clear(mod_hash_t *hash)
899 {
900 	ASSERT(hash);
901 	rw_enter(&hash->mh_contents, RW_WRITER);
902 	i_mod_hash_clear_nosync(hash);
903 	rw_exit(&hash->mh_contents);
904 }
905