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