xref: /titanic_51/usr/src/uts/common/os/modhash.c (revision 2fb4439d628ad2df0775287be1abd1ed95e7d267)
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
179 mod_hash_null_keydtor(mod_hash_key_t key)
180 {
181 }
182 
183 /*ARGSUSED*/
184 void
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
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
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
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
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 *
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
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
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
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 *
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
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
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
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
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 *
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
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
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 *
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 	rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL);
458 
459 	/*
460 	 * Link the hash up on the list of hashes
461 	 */
462 	mutex_enter(&mh_head_lock);
463 	mod_hash->mh_next = mh_head;
464 	mh_head = mod_hash;
465 	mutex_exit(&mh_head_lock);
466 
467 	return (mod_hash);
468 }
469 
470 /*
471  * mod_hash_destroy_hash()
472  * 	destroy a hash table, destroying all of its stored keys and values
473  * 	as well.
474  */
475 void
476 mod_hash_destroy_hash(mod_hash_t *hash)
477 {
478 	mod_hash_t *mhp, *mhpp;
479 
480 	mutex_enter(&mh_head_lock);
481 	/*
482 	 * Remove the hash from the hash list
483 	 */
484 	if (hash == mh_head) {		/* removing 1st list elem */
485 		mh_head = mh_head->mh_next;
486 	} else {
487 		/*
488 		 * mhpp can start out NULL since we know the 1st elem isn't the
489 		 * droid we're looking for.
490 		 */
491 		mhpp = NULL;
492 		for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
493 			if (mhp == hash) {
494 				mhpp->mh_next = mhp->mh_next;
495 				break;
496 			}
497 			mhpp = mhp;
498 		}
499 	}
500 	mutex_exit(&mh_head_lock);
501 
502 	/*
503 	 * Clean out keys and values.
504 	 */
505 	mod_hash_clear(hash);
506 
507 	rw_destroy(&hash->mh_contents);
508 
509 	kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
510 	kmem_free(hash, MH_SIZE(hash->mh_nchains));
511 }
512 
513 /*
514  * i_mod_hash()
515  * 	Call the hashing algorithm for this hash table, with the given key.
516  */
517 uint_t
518 i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
519 {
520 	uint_t h;
521 	/*
522 	 * Prevent div by 0 problems;
523 	 * Also a nice shortcut when using a hash as a list
524 	 */
525 	if (hash->mh_nchains == 1)
526 		return (0);
527 
528 	h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
529 	return (h % (hash->mh_nchains - 1));
530 }
531 
532 /*
533  * i_mod_hash_insert_nosync()
534  * mod_hash_insert()
535  * mod_hash_insert_reserve()
536  * 	insert 'val' into the hash table, using 'key' as its key.  If 'key' is
537  * 	already a key in the hash, an error will be returned, and the key-val
538  * 	pair will not be inserted.  i_mod_hash_insert_nosync() supports a simple
539  * 	handle abstraction, allowing hash entry allocation to be separated from
540  * 	the hash insertion.  this abstraction allows simple use of the mod_hash
541  * 	structure in situations where mod_hash_insert() with a KM_SLEEP
542  * 	allocation policy would otherwise be unsafe.
543  */
544 int
545 i_mod_hash_insert_nosync(mod_hash_t *hash, mod_hash_key_t key,
546     mod_hash_val_t val, mod_hash_hndl_t handle)
547 {
548 	uint_t hashidx;
549 	struct mod_hash_entry *entry;
550 
551 	ASSERT(hash);
552 
553 	/*
554 	 * If we've not been given reserved storage, allocate storage directly,
555 	 * using the hash's allocation policy.
556 	 */
557 	if (handle == (mod_hash_hndl_t)0) {
558 		entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
559 		if (entry == NULL) {
560 			hash->mh_stat.mhs_nomem++;
561 			return (MH_ERR_NOMEM);
562 		}
563 	} else {
564 		entry = (struct mod_hash_entry *)handle;
565 	}
566 
567 	hashidx = i_mod_hash(hash, key);
568 	entry->mhe_key = key;
569 	entry->mhe_val = val;
570 	entry->mhe_next = hash->mh_entries[hashidx];
571 
572 	hash->mh_entries[hashidx] = entry;
573 	hash->mh_stat.mhs_nelems++;
574 
575 	return (0);
576 }
577 
578 int
579 mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
580 {
581 	int res;
582 	mod_hash_val_t v;
583 
584 	rw_enter(&hash->mh_contents, RW_WRITER);
585 
586 	/*
587 	 * Disallow duplicate keys in the hash
588 	 */
589 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
590 		rw_exit(&hash->mh_contents);
591 		hash->mh_stat.mhs_coll++;
592 		return (MH_ERR_DUPLICATE);
593 	}
594 
595 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
596 	rw_exit(&hash->mh_contents);
597 
598 	return (res);
599 }
600 
601 int
602 mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
603     mod_hash_val_t val, mod_hash_hndl_t handle)
604 {
605 	int res;
606 	mod_hash_val_t v;
607 
608 	rw_enter(&hash->mh_contents, RW_WRITER);
609 
610 	/*
611 	 * Disallow duplicate keys in the hash
612 	 */
613 	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
614 		rw_exit(&hash->mh_contents);
615 		hash->mh_stat.mhs_coll++;
616 		return (MH_ERR_DUPLICATE);
617 	}
618 	res = i_mod_hash_insert_nosync(hash, key, val, handle);
619 	rw_exit(&hash->mh_contents);
620 
621 	return (res);
622 }
623 
624 /*
625  * mod_hash_reserve()
626  * mod_hash_reserve_nosleep()
627  * mod_hash_cancel()
628  *   Make or cancel a mod_hash_entry_t reservation.  Reservations are used in
629  *   mod_hash_insert_reserve() above.
630  */
631 int
632 mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
633 {
634 	*handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
635 	if (*handlep == NULL) {
636 		hash->mh_stat.mhs_nomem++;
637 		return (MH_ERR_NOMEM);
638 	}
639 
640 	return (0);
641 }
642 
643 int
644 mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
645 {
646 	*handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
647 	if (*handlep == NULL) {
648 		hash->mh_stat.mhs_nomem++;
649 		return (MH_ERR_NOMEM);
650 	}
651 
652 	return (0);
653 
654 }
655 
656 /*ARGSUSED*/
657 void
658 mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
659 {
660 	kmem_cache_free(mh_e_cache, *handlep);
661 	*handlep = (mod_hash_hndl_t)0;
662 }
663 
664 /*
665  * i_mod_hash_remove_nosync()
666  * mod_hash_remove()
667  * 	Remove an element from the hash table.
668  */
669 int
670 i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
671     mod_hash_val_t *val)
672 {
673 	int hashidx;
674 	struct mod_hash_entry *e, *ep;
675 
676 	hashidx = i_mod_hash(hash, key);
677 	ep = NULL; /* e's parent */
678 
679 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
680 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
681 			break;
682 		ep = e;
683 	}
684 
685 	if (e == NULL) {	/* not found */
686 		return (MH_ERR_NOTFOUND);
687 	}
688 
689 	if (ep == NULL) 	/* special case 1st element in bucket */
690 		hash->mh_entries[hashidx] = e->mhe_next;
691 	else
692 		ep->mhe_next = e->mhe_next;
693 
694 	/*
695 	 * Clean up resources used by the node's key.
696 	 */
697 	MH_KEY_DESTROY(hash, e->mhe_key);
698 
699 	*val = e->mhe_val;
700 	kmem_cache_free(mh_e_cache, e);
701 	hash->mh_stat.mhs_nelems--;
702 
703 	return (0);
704 }
705 
706 int
707 mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
708 {
709 	int res;
710 
711 	rw_enter(&hash->mh_contents, RW_WRITER);
712 	res = i_mod_hash_remove_nosync(hash, key, val);
713 	rw_exit(&hash->mh_contents);
714 
715 	return (res);
716 }
717 
718 /*
719  * mod_hash_replace()
720  * 	atomically remove an existing key-value pair from a hash, and replace
721  * 	the key and value with the ones supplied.  The removed key and value
722  * 	(if any) are destroyed.
723  */
724 int
725 mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
726 {
727 	int res;
728 	mod_hash_val_t v;
729 
730 	rw_enter(&hash->mh_contents, RW_WRITER);
731 
732 	if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
733 		/*
734 		 * mod_hash_remove() takes care of freeing up the key resources.
735 		 */
736 		MH_VAL_DESTROY(hash, v);
737 	}
738 	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
739 
740 	rw_exit(&hash->mh_contents);
741 
742 	return (res);
743 }
744 
745 /*
746  * mod_hash_destroy()
747  * 	Remove an element from the hash table matching 'key', and destroy it.
748  */
749 int
750 mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
751 {
752 	mod_hash_val_t val;
753 	int rv;
754 
755 	rw_enter(&hash->mh_contents, RW_WRITER);
756 
757 	if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
758 		/*
759 		 * mod_hash_remove() takes care of freeing up the key resources.
760 		 */
761 		MH_VAL_DESTROY(hash, val);
762 	}
763 
764 	rw_exit(&hash->mh_contents);
765 	return (rv);
766 }
767 
768 /*
769  * i_mod_hash_find_nosync()
770  * mod_hash_find()
771  * 	Find a value in the hash table corresponding to the given key.
772  */
773 int
774 i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
775     mod_hash_val_t *val)
776 {
777 	uint_t hashidx;
778 	struct mod_hash_entry *e;
779 
780 	hashidx = i_mod_hash(hash, key);
781 
782 	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
783 		if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
784 			*val = e->mhe_val;
785 			hash->mh_stat.mhs_hit++;
786 			return (0);
787 		}
788 	}
789 	hash->mh_stat.mhs_miss++;
790 	return (MH_ERR_NOTFOUND);
791 }
792 
793 int
794 mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
795 {
796 	int res;
797 
798 	rw_enter(&hash->mh_contents, RW_READER);
799 	res = i_mod_hash_find_nosync(hash, key, val);
800 	rw_exit(&hash->mh_contents);
801 
802 	return (res);
803 }
804 
805 int
806 mod_hash_find_cb(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
807     void (*find_cb)(mod_hash_key_t, mod_hash_val_t))
808 {
809 	int res;
810 
811 	rw_enter(&hash->mh_contents, RW_READER);
812 	res = i_mod_hash_find_nosync(hash, key, val);
813 	if (res == 0) {
814 		find_cb(key, *val);
815 	}
816 	rw_exit(&hash->mh_contents);
817 
818 	return (res);
819 }
820 
821 int
822 mod_hash_find_cb_rval(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val,
823     int (*find_cb)(mod_hash_key_t, mod_hash_val_t), int *cb_rval)
824 {
825 	int res;
826 
827 	rw_enter(&hash->mh_contents, RW_READER);
828 	res = i_mod_hash_find_nosync(hash, key, val);
829 	if (res == 0) {
830 		*cb_rval = find_cb(key, *val);
831 	}
832 	rw_exit(&hash->mh_contents);
833 
834 	return (res);
835 }
836 
837 void
838 i_mod_hash_walk_nosync(mod_hash_t *hash,
839     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
840 {
841 	struct mod_hash_entry	*e;
842 	uint_t			hashidx;
843 	int			res = MH_WALK_CONTINUE;
844 
845 	for (hashidx = 0;
846 	    (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
847 	    hashidx++) {
848 		e = hash->mh_entries[hashidx];
849 		while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
850 			res = callback(e->mhe_key, e->mhe_val, arg);
851 			e = e->mhe_next;
852 		}
853 	}
854 }
855 
856 /*
857  * mod_hash_walk()
858  * 	Walks all the elements in the hashtable and invokes the callback
859  * 	function with the key/value pair for each element.  The hashtable
860  * 	is locked for readers so the callback function should not attempt
861  * 	to do any updates to the hashable.  The callback function should
862  * 	return MH_WALK_CONTINUE to continue walking the hashtable or
863  * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
864  */
865 void
866 mod_hash_walk(mod_hash_t *hash,
867     uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
868 {
869 	rw_enter(&hash->mh_contents, RW_READER);
870 	i_mod_hash_walk_nosync(hash, callback, arg);
871 	rw_exit(&hash->mh_contents);
872 }
873 
874 
875 /*
876  * i_mod_hash_clear_nosync()
877  * mod_hash_clear()
878  *	Clears the given hash table by calling the destructor of every hash
879  *	element and freeing up all mod_hash_entry's.
880  */
881 void
882 i_mod_hash_clear_nosync(mod_hash_t *hash)
883 {
884 	int i;
885 	struct mod_hash_entry *e, *old_e;
886 
887 	for (i = 0; i < hash->mh_nchains; i++) {
888 		e = hash->mh_entries[i];
889 		while (e != NULL) {
890 			MH_KEY_DESTROY(hash, e->mhe_key);
891 			MH_VAL_DESTROY(hash, e->mhe_val);
892 			old_e = e;
893 			e = e->mhe_next;
894 			kmem_cache_free(mh_e_cache, old_e);
895 		}
896 		hash->mh_entries[i] = NULL;
897 	}
898 	hash->mh_stat.mhs_nelems = 0;
899 }
900 
901 void
902 mod_hash_clear(mod_hash_t *hash)
903 {
904 	ASSERT(hash);
905 	rw_enter(&hash->mh_contents, RW_WRITER);
906 	i_mod_hash_clear_nosync(hash);
907 	rw_exit(&hash->mh_contents);
908 }
909