summaryrefslogtreecommitdiffstats
path: root/module/icp/os/modhash.c
blob: 497e8439666570755464e9627be45923753eb56e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * mod_hash: flexible hash table implementation.
 *
 * This is a reasonably fast, reasonably flexible hash table implementation
 * which features pluggable hash algorithms to support storing arbitrary keys
 * and values.  It is designed to handle small (< 100,000 items) amounts of
 * data.  The hash uses chaining to resolve collisions, and does not feature a
 * mechanism to grow the hash.  Care must be taken to pick nchains to be large
 * enough for the application at hand, or lots of time will be wasted searching
 * hash chains.
 *
 * The client of the hash is required to supply a number of items to support
 * the various hash functions:
 *
 * 	- Destructor functions for the key and value being hashed.
 *	  A destructor is responsible for freeing an object when the hash
 *	  table is no longer storing it.  Since keys and values can be of
 *	  arbitrary type, separate destructors for keys & values are used.
 *	  These may be mod_hash_null_keydtor and mod_hash_null_valdtor if no
 *	  destructor is needed for either a key or value.
 *
 *	- A hashing algorithm which returns a uint_t representing a hash index
 *	  The number returned need _not_ be between 0 and nchains.  The mod_hash
 *	  code will take care of doing that.  The second argument (after the
 *	  key) to the hashing function is a void * that represents
 *	  hash_alg_data-- this is provided so that the hashing algrorithm can
 *	  maintain some state across calls, or keep algorithm-specific
 *	  constants associated with the hash table.
 *
 *	  A pointer-hashing and a string-hashing algorithm are supplied in
 *	  this file.
 *
 *	- A key comparator (a la qsort).
 *	  This is used when searching the hash chain.  The key comparator
 *	  determines if two keys match.  It should follow the return value
 *	  semantics of strcmp.
 *
 *	  string and pointer comparators are supplied in this file.
 *
 * mod_hash_create_strhash() and mod_hash_create_ptrhash() provide good
 * examples of how to create a customized hash table.
 *
 * Basic hash operations:
 *
 *   mod_hash_create_strhash(name, nchains, dtor),
 *	create a hash using strings as keys.
 *	NOTE: This create a hash which automatically cleans up the string
 *	      values it is given for keys.
 *
 *   mod_hash_create_ptrhash(name, nchains, dtor, key_elem_size):
 *	create a hash using pointers as keys.
 *
 *   mod_hash_create_extended(name, nchains, kdtor, vdtor,
 *			      hash_alg, hash_alg_data,
 *			      keycmp, sleep)
 *	create a customized hash table.
 *
 *   mod_hash_destroy_hash(hash):
 *	destroy the given hash table, calling the key and value destructors
 *	on each key-value pair stored in the hash.
 *
 *   mod_hash_insert(hash, key, val):
 *	place a key, value pair into the given hash.
 *	duplicate keys are rejected.
 *
 *   mod_hash_insert_reserve(hash, key, val, handle):
 *	place a key, value pair into the given hash, using handle to indicate
 *	the reserved storage for the pair.  (no memory allocation is needed
 *	during a mod_hash_insert_reserve.)  duplicate keys are rejected.
 *
 *   mod_hash_reserve(hash, *handle):
 *      reserve storage for a key-value pair using the memory allocation
 *      policy of 'hash', returning the storage handle in 'handle'.
 *
 *   mod_hash_reserve_nosleep(hash, *handle): reserve storage for a key-value
 *	pair ignoring the memory allocation policy of 'hash' and always without
 *	sleep, returning the storage handle in 'handle'.
 *
 *   mod_hash_remove(hash, key, *val):
 *	remove a key-value pair with key 'key' from 'hash', destroying the
 *	stored key, and returning the value in val.
 *
 *   mod_hash_replace(hash, key, val)
 * 	atomically remove an existing key-value pair from a hash, and replace
 * 	the key and value with the ones supplied.  The removed key and value
 * 	(if any) are destroyed.
 *
 *   mod_hash_destroy(hash, key):
 *	remove a key-value pair with key 'key' from 'hash', destroying both
 *	stored key and stored value.
 *
 *   mod_hash_find(hash, key, val):
 *	find a value in the hash table corresponding to the given key.
 *
 *   mod_hash_find_cb(hash, key, val, found_callback)
 *	find a value in the hash table corresponding to the given key.
 *	If a value is found, call specified callback passing key and val to it.
 *      The callback is called with the hash lock held.
 *	It is intended to be used in situations where the act of locating the
 *	data must also modify it - such as in reference counting schemes.
 *
 *   mod_hash_walk(hash, callback(key, elem, arg), arg)
 * 	walks all the elements in the hashtable and invokes the callback
 * 	function with the key/value pair for each element.  the hashtable
 * 	is locked for readers so the callback function should not attempt
 * 	to do any updates to the hashable.  the callback function should
 * 	return MH_WALK_CONTINUE to continue walking the hashtable or
 * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
 *
 *   mod_hash_clear(hash):
 *	clears the given hash table of entries, calling the key and value
 *	destructors for every element in the hash.
 */

#include <sys/zfs_context.h>
#include <sys/bitmap.h>
#include <sys/modhash_impl.h>
#include <sys/sysmacros.h>

/*
 * MH_KEY_DESTROY()
 * 	Invoke the key destructor.
 */
#define	MH_KEY_DESTROY(hash, key) ((hash->mh_kdtor)(key))

/*
 * MH_VAL_DESTROY()
 * 	Invoke the value destructor.
 */
#define	MH_VAL_DESTROY(hash, val) ((hash->mh_vdtor)(val))

/*
 * MH_KEYCMP()
 * 	Call the key comparator for the given hash keys.
 */
#define	MH_KEYCMP(hash, key1, key2) ((hash->mh_keycmp)(key1, key2))

/*
 * Cache for struct mod_hash_entry
 */
kmem_cache_t *mh_e_cache = NULL;
mod_hash_t *mh_head = NULL;
kmutex_t mh_head_lock;

/*
 * mod_hash_null_keydtor()
 * mod_hash_null_valdtor()
 * 	no-op key and value destructors.
 */
/*ARGSUSED*/
void
mod_hash_null_keydtor(mod_hash_key_t key)
{
}

/*ARGSUSED*/
void
mod_hash_null_valdtor(mod_hash_val_t val)
{
}

/*
 * mod_hash_bystr()
 * mod_hash_strkey_cmp()
 * mod_hash_strkey_dtor()
 * mod_hash_strval_dtor()
 *	Hash and key comparison routines for hashes with string keys.
 *
 * mod_hash_create_strhash()
 * 	Create a hash using strings as keys
 *
 *	The string hashing algorithm is from the "Dragon Book" --
 *	"Compilers: Principles, Tools & Techniques", by Aho, Sethi, Ullman
 */

/*ARGSUSED*/
uint_t
mod_hash_bystr(void *hash_data, mod_hash_key_t key)
{
	uint_t hash = 0;
	uint_t g;
	char *p, *k = (char *)key;

	ASSERT(k);
	for (p = k; *p != '\0'; p++) {
		hash = (hash << 4) + *p;
		if ((g = (hash & 0xf0000000)) != 0) {
			hash ^= (g >> 24);
			hash ^= g;
		}
	}
	return (hash);
}

int
mod_hash_strkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	return (strcmp((char *)key1, (char *)key2));
}

void
mod_hash_strkey_dtor(mod_hash_key_t key)
{
	char *c = (char *)key;
	kmem_free(c, strlen(c) + 1);
}

void
mod_hash_strval_dtor(mod_hash_val_t val)
{
	char *c = (char *)val;
	kmem_free(c, strlen(c) + 1);
}

mod_hash_t *
mod_hash_create_strhash_nodtr(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t))
{
	return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
	    val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
}

mod_hash_t *
mod_hash_create_strhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t))
{
	return mod_hash_create_extended(name, nchains, mod_hash_strkey_dtor,
	    val_dtor, mod_hash_bystr, NULL, mod_hash_strkey_cmp, KM_SLEEP);
}

void
mod_hash_destroy_strhash(mod_hash_t *strhash)
{
	ASSERT(strhash);
	mod_hash_destroy_hash(strhash);
}


/*
 * mod_hash_byptr()
 * mod_hash_ptrkey_cmp()
 *	Hash and key comparison routines for hashes with pointer keys.
 *
 * mod_hash_create_ptrhash()
 * mod_hash_destroy_ptrhash()
 * 	Create a hash that uses pointers as keys.  This hash algorithm
 * 	picks an appropriate set of middle bits in the address to hash on
 * 	based on the size of the hash table and a hint about the size of
 * 	the items pointed at.
 */
uint_t
mod_hash_byptr(void *hash_data, mod_hash_key_t key)
{
	uintptr_t k = (uintptr_t)key;
	k >>= (int)(uintptr_t)hash_data;

	return ((uint_t)k);
}

int
mod_hash_ptrkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	uintptr_t k1 = (uintptr_t)key1;
	uintptr_t k2 = (uintptr_t)key2;
	if (k1 > k2)
		return (-1);
	else if (k1 < k2)
		return (1);
	else
		return (0);
}

mod_hash_t *
mod_hash_create_ptrhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t), size_t key_elem_size)
{
	size_t rshift;

	/*
	 * We want to hash on the bits in the middle of the address word
	 * Bits far to the right in the word have little significance, and
	 * are likely to all look the same (for example, an array of
	 * 256-byte structures will have the bottom 8 bits of address
	 * words the same).  So we want to right-shift each address to
	 * ignore the bottom bits.
	 *
	 * The high bits, which are also unused, will get taken out when
	 * mod_hash takes hashkey % nchains.
	 */
	rshift = highbit64(key_elem_size);

	return mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
	    val_dtor, mod_hash_byptr, (void *)rshift, mod_hash_ptrkey_cmp,
	    KM_SLEEP);
}

void
mod_hash_destroy_ptrhash(mod_hash_t *hash)
{
	ASSERT(hash);
	mod_hash_destroy_hash(hash);
}

/*
 * mod_hash_byid()
 * mod_hash_idkey_cmp()
 *	Hash and key comparison routines for hashes with 32-bit unsigned keys.
 *
 * mod_hash_create_idhash()
 * mod_hash_destroy_idhash()
 * mod_hash_iddata_gen()
 * 	Create a hash that uses numeric keys.
 *
 *	The hash algorithm is documented in "Introduction to Algorithms"
 *	(Cormen, Leiserson, Rivest);  when the hash table is created, it
 *	attempts to find the next largest prime above the number of hash
 *	slots.  The hash index is then this number times the key modulo
 *	the hash size, or (key * prime) % nchains.
 */
uint_t
mod_hash_byid(void *hash_data, mod_hash_key_t key)
{
	uint_t kval = (uint_t)(uintptr_t)hash_data;
	return ((uint_t)(uintptr_t)key * (uint_t)kval);
}

int
mod_hash_idkey_cmp(mod_hash_key_t key1, mod_hash_key_t key2)
{
	return ((uint_t)(uintptr_t)key1 - (uint_t)(uintptr_t)key2);
}

/*
 * Generate the next largest prime number greater than nchains; this value
 * is intended to be later passed in to mod_hash_create_extended() as the
 * hash_data.
 */
uint_t
mod_hash_iddata_gen(size_t nchains)
{
	uint_t kval, i, prime;

	/*
	 * Pick the first (odd) prime greater than nchains.  Make sure kval is
	 * odd (so start with nchains +1 or +2 as appropriate).
	 */
	kval = (nchains % 2 == 0) ? nchains + 1 : nchains + 2;

	for (;;) {
		prime = 1;
		for (i = 3; i * i <= kval; i += 2) {
			if (kval % i == 0)
				prime = 0;
		}
		if (prime == 1)
			break;
		kval += 2;
	}
	return (kval);
}

mod_hash_t *
mod_hash_create_idhash(char *name, size_t nchains,
    void (*val_dtor)(mod_hash_val_t))
{
	uint_t kval = mod_hash_iddata_gen(nchains);

	return (mod_hash_create_extended(name, nchains, mod_hash_null_keydtor,
	    val_dtor, mod_hash_byid, (void *)(uintptr_t)kval,
	    mod_hash_idkey_cmp, KM_SLEEP));
}

void
mod_hash_destroy_idhash(mod_hash_t *hash)
{
	ASSERT(hash);
	mod_hash_destroy_hash(hash);
}

void
mod_hash_fini(void)
{
	mutex_destroy(&mh_head_lock);

	if (mh_e_cache) {
		kmem_cache_destroy(mh_e_cache);
		mh_e_cache = NULL;
	}
}

/*
 * mod_hash_init()
 * 	sets up globals, etc for mod_hash_*
 */
void
mod_hash_init(void)
{
	ASSERT(mh_e_cache == NULL);
	mh_e_cache = kmem_cache_create("mod_hash_entries",
	    sizeof (struct mod_hash_entry), 0, NULL, NULL, NULL, NULL,
	    NULL, 0);

	mutex_init(&mh_head_lock, NULL, MUTEX_DEFAULT, NULL);
}

/*
 * mod_hash_create_extended()
 * 	The full-blown hash creation function.
 *
 * notes:
 * 	nchains		- how many hash slots to create.  More hash slots will
 *			  result in shorter hash chains, but will consume
 *			  slightly more memory up front.
 *	sleep		- should be KM_SLEEP or KM_NOSLEEP, to indicate whether
 *			  to sleep for memory, or fail in low-memory conditions.
 *
 * 	Fails only if KM_NOSLEEP was specified, and no memory was available.
 */
mod_hash_t *
mod_hash_create_extended(
    char *hname,			/* descriptive name for hash */
    size_t nchains,			/* number of hash slots */
    void (*kdtor)(mod_hash_key_t),	/* key destructor */
    void (*vdtor)(mod_hash_val_t),	/* value destructor */
    uint_t (*hash_alg)(void *, mod_hash_key_t), /* hash algorithm */
    void *hash_alg_data,		/* pass-thru arg for hash_alg */
    int (*keycmp)(mod_hash_key_t, mod_hash_key_t), /* key comparator */
    int sleep)				/* whether to sleep for mem */
{
	mod_hash_t *mod_hash;
	ASSERT(hname && keycmp && hash_alg && vdtor && kdtor);

	if ((mod_hash = kmem_zalloc(MH_SIZE(nchains), sleep)) == NULL)
		return (NULL);

	mod_hash->mh_name = kmem_alloc(strlen(hname) + 1, sleep);
	if (mod_hash->mh_name == NULL) {
		kmem_free(mod_hash, MH_SIZE(nchains));
		return (NULL);
	}
	(void) strcpy(mod_hash->mh_name, hname);

	rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL);
	mod_hash->mh_sleep = sleep;
	mod_hash->mh_nchains = nchains;
	mod_hash->mh_kdtor = kdtor;
	mod_hash->mh_vdtor = vdtor;
	mod_hash->mh_hashalg = hash_alg;
	mod_hash->mh_hashalg_data = hash_alg_data;
	mod_hash->mh_keycmp = keycmp;

	/*
	 * Link the hash up on the list of hashes
	 */
	mutex_enter(&mh_head_lock);
	mod_hash->mh_next = mh_head;
	mh_head = mod_hash;
	mutex_exit(&mh_head_lock);

	return (mod_hash);
}

/*
 * mod_hash_destroy_hash()
 * 	destroy a hash table, destroying all of its stored keys and values
 * 	as well.
 */
void
mod_hash_destroy_hash(mod_hash_t *hash)
{
	mod_hash_t *mhp, *mhpp;

	mutex_enter(&mh_head_lock);
	/*
	 * Remove the hash from the hash list
	 */
	if (hash == mh_head) {		/* removing 1st list elem */
		mh_head = mh_head->mh_next;
	} else {
		/*
		 * mhpp can start out NULL since we know the 1st elem isn't the
		 * droid we're looking for.
		 */
		mhpp = NULL;
		for (mhp = mh_head; mhp != NULL; mhp = mhp->mh_next) {
			if (mhp == hash) {
				mhpp->mh_next = mhp->mh_next;
				break;
			}
			mhpp = mhp;
		}
	}
	mutex_exit(&mh_head_lock);

	/*
	 * Clean out keys and values.
	 */
	mod_hash_clear(hash);

	rw_destroy(&hash->mh_contents);
	kmem_free(hash->mh_name, strlen(hash->mh_name) + 1);
	kmem_free(hash, MH_SIZE(hash->mh_nchains));
}

/*
 * i_mod_hash()
 * 	Call the hashing algorithm for this hash table, with the given key.
 */
uint_t
i_mod_hash(mod_hash_t *hash, mod_hash_key_t key)
{
	uint_t h;
	/*
	 * Prevent div by 0 problems;
	 * Also a nice shortcut when using a hash as a list
	 */
	if (hash->mh_nchains == 1)
		return (0);

	h = (hash->mh_hashalg)(hash->mh_hashalg_data, key);
	return (h % (hash->mh_nchains - 1));
}

/*
 * i_mod_hash_insert_nosync()
 * mod_hash_insert()
 * mod_hash_insert_reserve()
 * 	insert 'val' into the hash table, using 'key' as its key.  If 'key' is
 * 	already a key in the hash, an error will be returned, and the key-val
 * 	pair will not be inserted.  i_mod_hash_insert_nosync() supports a simple
 * 	handle abstraction, allowing hash entry allocation to be separated from
 * 	the hash insertion.  this abstraction allows simple use of the mod_hash
 * 	structure in situations where mod_hash_insert() with a KM_SLEEP
 * 	allocation policy would otherwise be unsafe.
 */
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)
{
	uint_t hashidx;
	struct mod_hash_entry *entry;

	ASSERT(hash);

	/*
	 * If we've not been given reserved storage, allocate storage directly,
	 * using the hash's allocation policy.
	 */
	if (handle == (mod_hash_hndl_t)0) {
		entry = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
		if (entry == NULL) {
			hash->mh_stat.mhs_nomem++;
			return (MH_ERR_NOMEM);
		}
	} else {
		entry = (struct mod_hash_entry *)handle;
	}

	hashidx = i_mod_hash(hash, key);
	entry->mhe_key = key;
	entry->mhe_val = val;
	entry->mhe_next = hash->mh_entries[hashidx];

	hash->mh_entries[hashidx] = entry;
	hash->mh_stat.mhs_nelems++;

	return (0);
}

int
mod_hash_insert(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	/*
	 * Disallow duplicate keys in the hash
	 */
	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
		rw_exit(&hash->mh_contents);
		hash->mh_stat.mhs_coll++;
		return (MH_ERR_DUPLICATE);
	}

	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);
	rw_exit(&hash->mh_contents);

	return (res);
}

int
mod_hash_insert_reserve(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t val, mod_hash_hndl_t handle)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	/*
	 * Disallow duplicate keys in the hash
	 */
	if (i_mod_hash_find_nosync(hash, key, &v) == 0) {
		rw_exit(&hash->mh_contents);
		hash->mh_stat.mhs_coll++;
		return (MH_ERR_DUPLICATE);
	}
	res = i_mod_hash_insert_nosync(hash, key, val, handle);
	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_reserve()
 * mod_hash_reserve_nosleep()
 * mod_hash_cancel()
 *   Make or cancel a mod_hash_entry_t reservation.  Reservations are used in
 *   mod_hash_insert_reserve() above.
 */
int
mod_hash_reserve(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	*handlep = kmem_cache_alloc(mh_e_cache, hash->mh_sleep);
	if (*handlep == NULL) {
		hash->mh_stat.mhs_nomem++;
		return (MH_ERR_NOMEM);
	}

	return (0);
}

int
mod_hash_reserve_nosleep(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	*handlep = kmem_cache_alloc(mh_e_cache, KM_NOSLEEP);
	if (*handlep == NULL) {
		hash->mh_stat.mhs_nomem++;
		return (MH_ERR_NOMEM);
	}

	return (0);

}

/*ARGSUSED*/
void
mod_hash_cancel(mod_hash_t *hash, mod_hash_hndl_t *handlep)
{
	kmem_cache_free(mh_e_cache, *handlep);
	*handlep = (mod_hash_hndl_t)0;
}

/*
 * i_mod_hash_remove_nosync()
 * mod_hash_remove()
 * 	Remove an element from the hash table.
 */
int
i_mod_hash_remove_nosync(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t *val)
{
	int hashidx;
	struct mod_hash_entry *e, *ep;

	hashidx = i_mod_hash(hash, key);
	ep = NULL; /* e's parent */

	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
		if (MH_KEYCMP(hash, e->mhe_key, key) == 0)
			break;
		ep = e;
	}

	if (e == NULL) {	/* not found */
		return (MH_ERR_NOTFOUND);
	}

	if (ep == NULL) 	/* special case 1st element in bucket */
		hash->mh_entries[hashidx] = e->mhe_next;
	else
		ep->mhe_next = e->mhe_next;

	/*
	 * Clean up resources used by the node's key.
	 */
	MH_KEY_DESTROY(hash, e->mhe_key);

	*val = e->mhe_val;
	kmem_cache_free(mh_e_cache, e);
	hash->mh_stat.mhs_nelems--;

	return (0);
}

int
mod_hash_remove(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
{
	int res;

	rw_enter(&hash->mh_contents, RW_WRITER);
	res = i_mod_hash_remove_nosync(hash, key, val);
	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_replace()
 * 	atomically remove an existing key-value pair from a hash, and replace
 * 	the key and value with the ones supplied.  The removed key and value
 * 	(if any) are destroyed.
 */
int
mod_hash_replace(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t val)
{
	int res;
	mod_hash_val_t v;

	rw_enter(&hash->mh_contents, RW_WRITER);

	if (i_mod_hash_remove_nosync(hash, key, &v) == 0) {
		/*
		 * mod_hash_remove() takes care of freeing up the key resources.
		 */
		MH_VAL_DESTROY(hash, v);
	}
	res = i_mod_hash_insert_nosync(hash, key, val, (mod_hash_hndl_t)0);

	rw_exit(&hash->mh_contents);

	return (res);
}

/*
 * mod_hash_destroy()
 * 	Remove an element from the hash table matching 'key', and destroy it.
 */
int
mod_hash_destroy(mod_hash_t *hash, mod_hash_key_t key)
{
	mod_hash_val_t val;
	int rv;

	rw_enter(&hash->mh_contents, RW_WRITER);

	if ((rv = i_mod_hash_remove_nosync(hash, key, &val)) == 0) {
		/*
		 * mod_hash_remove() takes care of freeing up the key resources.
		 */
		MH_VAL_DESTROY(hash, val);
	}

	rw_exit(&hash->mh_contents);
	return (rv);
}

/*
 * i_mod_hash_find_nosync()
 * mod_hash_find()
 * 	Find a value in the hash table corresponding to the given key.
 */
int
i_mod_hash_find_nosync(mod_hash_t *hash, mod_hash_key_t key,
    mod_hash_val_t *val)
{
	uint_t hashidx;
	struct mod_hash_entry *e;

	hashidx = i_mod_hash(hash, key);

	for (e = hash->mh_entries[hashidx]; e != NULL; e = e->mhe_next) {
		if (MH_KEYCMP(hash, e->mhe_key, key) == 0) {
			*val = e->mhe_val;
			hash->mh_stat.mhs_hit++;
			return (0);
		}
	}
	hash->mh_stat.mhs_miss++;
	return (MH_ERR_NOTFOUND);
}

int
mod_hash_find(mod_hash_t *hash, mod_hash_key_t key, mod_hash_val_t *val)
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	rw_exit(&hash->mh_contents);

	return (res);
}

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))
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	if (res == 0) {
		find_cb(key, *val);
	}
	rw_exit(&hash->mh_contents);

	return (res);
}

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)
{
	int res;

	rw_enter(&hash->mh_contents, RW_READER);
	res = i_mod_hash_find_nosync(hash, key, val);
	if (res == 0) {
		*cb_rval = find_cb(key, *val);
	}
	rw_exit(&hash->mh_contents);

	return (res);
}

void
i_mod_hash_walk_nosync(mod_hash_t *hash,
    uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
{
	struct mod_hash_entry	*e;
	uint_t			hashidx;
	int			res = MH_WALK_CONTINUE;

	for (hashidx = 0;
	    (hashidx < (hash->mh_nchains - 1)) && (res == MH_WALK_CONTINUE);
	    hashidx++) {
		e = hash->mh_entries[hashidx];
		while ((e != NULL) && (res == MH_WALK_CONTINUE)) {
			res = callback(e->mhe_key, e->mhe_val, arg);
			e = e->mhe_next;
		}
	}
}

/*
 * mod_hash_walk()
 * 	Walks all the elements in the hashtable and invokes the callback
 * 	function with the key/value pair for each element.  The hashtable
 * 	is locked for readers so the callback function should not attempt
 * 	to do any updates to the hashable.  The callback function should
 * 	return MH_WALK_CONTINUE to continue walking the hashtable or
 * 	MH_WALK_TERMINATE to abort the walk of the hashtable.
 */
void
mod_hash_walk(mod_hash_t *hash,
    uint_t (*callback)(mod_hash_key_t, mod_hash_val_t *, void *), void *arg)
{
	rw_enter(&hash->mh_contents, RW_READER);
	i_mod_hash_walk_nosync(hash, callback, arg);
	rw_exit(&hash->mh_contents);
}


/*
 * i_mod_hash_clear_nosync()
 * mod_hash_clear()
 *	Clears the given hash table by calling the destructor of every hash
 *	element and freeing up all mod_hash_entry's.
 */
void
i_mod_hash_clear_nosync(mod_hash_t *hash)
{
	int i;
	struct mod_hash_entry *e, *old_e;

	for (i = 0; i < hash->mh_nchains; i++) {
		e = hash->mh_entries[i];
		while (e != NULL) {
			MH_KEY_DESTROY(hash, e->mhe_key);
			MH_VAL_DESTROY(hash, e->mhe_val);
			old_e = e;
			e = e->mhe_next;
			kmem_cache_free(mh_e_cache, old_e);
		}
		hash->mh_entries[i] = NULL;
	}
	hash->mh_stat.mhs_nelems = 0;
}

void
mod_hash_clear(mod_hash_t *hash)
{
	ASSERT(hash);
	rw_enter(&hash->mh_contents, RW_WRITER);
	i_mod_hash_clear_nosync(hash);
	rw_exit(&hash->mh_contents);
}