Merge commit 'b1e7e97d3b60469b243b3b2e22c7d8cbd11c7c90'

[unleashed.git] / kernel / os / modhash.c

/*
 * 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/bitmap.h>
#include <sys/debug.h>
#include <sys/kmem.h>
#include <sys/sunddi.h>

#include <sys/modhash_impl.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(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 = highbit(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);
}

/*
 * 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);
}

/*
 * 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);

        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;

        rw_init(&mod_hash->mh_contents, NULL, RW_DEFAULT, NULL);

        /*
         * 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);
}