lib/libnisdb/nis_hashitem.c

	nis_hashitem.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (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 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

#include <string.h>
#include <pthread.h>
#include <syslog.h>
#include <rpcsvc/nis.h>

#include "nis_hashitem.h"

/* We're the magician, so undefine the define-magic */
#undef  NIS_HASH_ITEM
#undef  NIS_HASH_TABLE
#undef  nis_insert_item
#undef  nis_find_item
#undef  nis_pop_item
#undef  nis_remove_item

#define set_thread_status(msg, state)

/*
 * The hash table routines below implement nested (or recursive)
 * one-writer-or-many-readers locking. The following restrictions
 * exist:
 *
 *  Unless an item destructor has been established, an item
 *  MUST NOT be removed from a list (__nis_pop_item_mt() or
 *  (__nis_remove_item_mt()) when the thread performing
 *  the deletion is holding a read-only lock on the item.
 *  Doing so will result in the thread blocking in
 *  pthread_cond_wait() waiting for itself to signal on
 *  the condition variable. Deletion when the invoking
 *  thread is holding a write lock (any level of nesting),
 *  or no lock, is OK.
 */

void
__nis_init_hash_table(__nis_hash_table_mt *table,
            void (*itemDestructor)(void *)) {

    if (table != 0) {
        (void) pthread_mutex_init(&table->lock, 0);
        (void) pthread_cond_init(&table->cond, 0);
        (void) pthread_mutex_init(&table->traverser_id_lock, 0);
        table->traversed = 0;
        table->locked_items = 0;
        (void) memset(table->keys, 0, sizeof (table->keys));
        table->first = 0;
        table->destroyItem = itemDestructor;
    }
}

int
__nis_lock_hash_table(__nis_hash_table_mt *table, int traverse, char *msg) {

    pthread_t   myself = pthread_self();

    if (table != 0) {
        if (traverse) {
            /*
             * We want exclusive access to everything in the
             * table (list). Wait until there are no threads
             * either traversing the list, or with exclusive
             * access to an item.
             */
            set_thread_status(msg, "table WL");
            (void) pthread_mutex_lock(&table->lock);
            set_thread_status(msg, "table L");
            while ((table->traversed != 0 &&
                    table->traverser_id != myself) ||
                table->locked_items != 0) {
                set_thread_status(msg, "traverse cond_wait");
                MT_LOG(1, (LOG_NOTICE,
                    "%d: lh table 0x%x trav cond wait",
                    myself, table));
                (void) pthread_cond_wait(&table->cond,
                            &table->lock);
            }
            set_thread_status(msg, "traverser_id WL");
            (void) pthread_mutex_lock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id L");
            table->traversed = 1;
            table->traverser_id = myself;
            (void) pthread_mutex_unlock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id U");
        } else {
            /*
             * Called from the nis_*_item() functions. If no one's
             * locked the table, lock it. If the table already is
             * being traversed by us, do nothing. Otherwise, wait
             * for the lock.
             */
            set_thread_status(msg, "non-traverse TL");
            if (pthread_mutex_trylock(&table->lock) == EBUSY) {
                int dolock = 1;
                /* Already locked; find out if it's us */
                set_thread_status(msg, "traverser_id L");
                (void) pthread_mutex_lock(
                        &table->traverser_id_lock);
                if (table->traversed != 0 &&
                    table->traverser_id == myself) {
                    /* It's us. No action. */
                    dolock = 0;
                }
                (void) pthread_mutex_unlock(
                        &table->traverser_id_lock);
                set_thread_status(msg, "traverser_id U");
                /* Not us. Wait for the lock */
                if (dolock) {
                    MT_LOG(1, (LOG_NOTICE,
                    "%d: lh table 0x%x cond wait",
                        myself, table));
                    set_thread_status(msg, "table WL");
                    (void) pthread_mutex_lock(&table->lock);
                    set_thread_status(msg, "table L");
                }
            }
        }
        MT_LOG(1, (LOG_NOTICE, "%d: lh table %s lock acquired 0x%x",
        myself, traverse?"traverse":"non-traverse", table));
        return (1);
    } else {
        return (0);
    }
}

int
__nis_ulock_hash_table(__nis_hash_table_mt *table, int traverse, char *msg) {

    int dounlock = 0;

    if (table != 0) {
        if (traverse) {
            /*
             * Since we're keeping track of who's traversing the
             * table in order to avoid recursive locking in the
             * nis_*item() functions, we might as well sanity check
             * here.
             */
            set_thread_status(msg, "traverser_id WL");
            (void) pthread_mutex_lock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id L");
            if (table->traversed != 0 &&
                table->traverser_id == pthread_self()) {
                table->traversed = 0;
                /*
                 * Leave traverser_id as it is, so that it
                 * possible to see which thread last held
                 * the traverser lock.
                 */
                dounlock = 1;
                /* Wake up other traversers-to-be */
                set_thread_status(msg, "table cond_signal");
                (void) pthread_cond_signal(&table->cond);
            }
            (void) pthread_mutex_unlock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id U");
        } else {
            /*
             * Called from the nis_*_item() functions. If we're
             * traversing the table, leave it locked.
             */
            set_thread_status(msg, "traverser_id WL");
            (void) pthread_mutex_lock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id L");
            if (table->traversed == 0) {
                dounlock = 1;
            }
            (void) pthread_mutex_unlock(&table->traverser_id_lock);
            set_thread_status(msg, "traverser_id U");
        }
        if (dounlock) {
            (void) pthread_mutex_unlock(&table->lock);
            set_thread_status(msg, "table U");
        }
        MT_LOG(1, (LOG_NOTICE, "%d: lh table %s release 0x%x (%s)",
        pthread_self(), traverse?"traverse":"non-traverse", table,
            dounlock?"unlocked":"still held"));
        return (1);
    } else {
        return (0);
    }
}

static __nis_hash_item_mt **
__find_item_mt(nis_name name, __nis_hash_table_mt *table, int *keyp) {

    int         key = 0;
    unsigned char       *s;
    __nis_hash_item_mt  *it, **pp;

    /* Assume table!=0, table lock held */

    for (s = (unsigned char *)name;  *s != 0;  s++) {
        key += *s;
    }
    key %= (sizeof (table->keys) / sizeof (table->keys[0]));

    if (keyp != 0) {
        *keyp = key;
    }
    for (pp = &table->keys[key];  (it = *pp) != 0;  pp = &it->next) {
        if (strcmp(name, it->name) == 0) {
            break;
        }
    }

    return (pp);
}

/*
 * The 'readwrite' argument is interpreted as follows on a successful
 * return:
 *
 *  < 0 Exclusive access to item
 *  0   Item must not be used or referenced in any way
 *  > 0 Non-exclusive access (read-only) to item
 *
 * Except when 'readwrite' ==  0, the caller must explicitly release the
 * item (__nis_release_item()).
 */
int
__nis_insert_item_mt(void *arg, __nis_hash_table_mt *table, int readwrite) {

    __nis_hash_item_mt  *item = arg;
    int         key;
    __nis_hash_item_mt  **pp;

    if (item == 0 || __nis_lock_hash_table(table, 0, "nitmt") == 0)
        return (0);

    if ((*(pp = __find_item_mt(item->name, table, &key))) != 0) {
        (void) __nis_ulock_hash_table(table, 0, "nitmt");
        return (0);
    }

    (void) pthread_cond_init(&item->lock, 0);
    item->readers = item->writer = 0;
    item->last_reader_id = item->writer_id = INV_PTHREAD_ID;
    if (readwrite < 0) {
        item->writer = 1;
        item->writer_id = pthread_self();
        table->locked_items++;
    } else if (readwrite > 0) {
        item->readers = 1;
        item->last_reader_id = pthread_self();
        table->locked_items++;
    }
    item->next  = *pp;
    *pp     = item;
    item->keychain  = key;

    if (table->first)
        table->first->prv_item = item;

    item->nxt_item  = table->first;
    item->prv_item  = NULL;
    table->first    = item;

    (void) __nis_ulock_hash_table(table, 0, "nitmt");

    return (1);
}

void
__nis_insert_name_mt(nis_name name, __nis_hash_table_mt *table) {

    __nis_hash_item_mt  *item;

    if (name == 0 || table == 0)
        return;

    if ((item = malloc(sizeof (*item))) == 0) {
        syslog(LOG_WARNING, "__nis_insert_name_mt: malloc failed\n");
        return;
    }

    if ((item->name = strdup(name)) == 0) {
        syslog(LOG_WARNING, "__nis_insert_name_mt: strdup failed\n");
        free(item);
        return;
    }

    if (! __nis_insert_item_mt(item, table, 0)) {
        free(item->name);
        free(item);
    }
}

/*
 * readwrite:   < 0 Exclusive access
 *      0   No access; must not use returned item in any way,
 *          other than to confirm existence indicated by a non-NULL
 *          return value.
 *      > 0 Non-exclusive (read-only) access
 *
 * If trylock != 0 and *trylock != 0 and the item exists but the requested
 * lock type cannot be acquired, set *trylock = -1 and return 0.
 */
void *
__nis_find_item_mt(nis_name name, __nis_hash_table_mt *table, int readwrite,
            int *trylock) {

    __nis_hash_item_mt  *item;
    pthread_t       me = pthread_self();

    if (name == 0 || __nis_lock_hash_table(table, 0, "nfimt") == 0)
        return (0);

    /*
     * Block waiting for more favorable conditions unless:
     *
     *  The item doesn't exist anymore
     *
     *  'readwrite' == 0 (verify existence only)
     *
     *  There's a writer, but it's us
     *
     *  There are no writers, and we're satisfied by RO access
     *
     *  A trylock was requested
     */
    while ((item = *__find_item_mt(name, table, 0)) != 0) {
        if (readwrite == 0 ||
                (item->writer == 0 && item->readers == 0))
            break;
        if (item->writer == 0 && readwrite > 0)
            break;
        if ((item->writer != 0 && item->writer_id == me))
            break;
        if (trylock != 0 && *trylock != 0) {
            *trylock = -1;
            (void) __nis_ulock_hash_table(table, 0, "nfimt");
            return (0);
        }
        (void) pthread_cond_wait(&item->lock, &table->lock);
    }

    if (item != 0) {
        if (readwrite < 0) {
            if (item->writer == 0) {
                item->writer_id = me;
                table->locked_items++;
            }
            item->writer++;
        } else if (readwrite > 0) {
            if (item->readers == 0) {
                table->locked_items++;
            }
            item->last_reader_id = me;
            item->readers++;
        }
    }

    (void) __nis_ulock_hash_table(table, 0, "nfimt");

    return (item);
}

void *
__nis_pop_item_mt(__nis_hash_table_mt *table) {

    __nis_hash_item_mt  *item, *cur, *prev;
    pthread_t       mtid;

    if (__nis_lock_hash_table(table, 0, "npimt") == 0)
        return (0);

    /* Wait until the first item isn't in use by another thread */
    mtid = pthread_self();
    while ((item = table->first) != 0) {
        if (table->destroyItem != 0)
            break;
        if (item->readers == 0 && item->writer == 0)
            break;
        if (item->writer != 0 && item->writer_id == mtid)
            break;
        (void) pthread_cond_wait(&item->lock, &table->lock);
    }

    /* List might be empty now */
    if (item == 0) {
        __nis_ulock_hash_table(table, 0, "npimt");
        return (0);
    }

    prev = 0;
    for (cur = table->keys[item->keychain]; cur;
                    prev = cur, cur = cur->next) {
        if (cur == item) {
            if (prev)
                prev->next = cur->next;
            else
                table->keys[cur->keychain] = cur->next;
            if (cur->prv_item)
                cur->prv_item->nxt_item = cur->nxt_item;
            else
                table->first = cur->nxt_item;
            if (cur->nxt_item)
                cur->nxt_item->prv_item = cur->prv_item;
            break;
        }
    }

    /*
     * We use keychain < 0 to indicate that the item isn't linked
     * into the table anymore.
     */
    item->keychain = -1;

    /* Adjust the count of locked items in the table */
    if (table->locked_items != 0 &&
            (item->writer > 0 || item->readers > 0)) {
        table->locked_items--;
        if (table->locked_items == 0) {
            /* Wake up traversers-to-be */
            (void) pthread_cond_signal(&table->cond);
        }
    }

    /*
     * Wake up any threads that were waiting for this item. Obviously,
     * such threads must start over scanning the list.
     */
    (void) pthread_cond_signal(&item->lock);
    (void) pthread_cond_destroy(&item->lock);

    /*
     * If the item isn't locked, and an item destructor has been
     * established, invoke the destructor.
     */
    if (item->readers == 0 && item->writer == 0 &&
            table->destroyItem != 0) {
        (*table->destroyItem)(item);
        item = 0;
    } else {
        item->next = 0;
        item->prv_item = 0;
        item->nxt_item = 0;
    }

    (void) __nis_ulock_hash_table(table, 0, "npimt");

    /*
     * If we get here, and the 'item' is NULL, we've popped the
     * item, but also destroyed it. Returning NULL would make
     * our caller believe the list is empty, so instead, we invoke
     * ourselves to pop the next item.
     */
    return ((item != 0) ? item : __nis_pop_item_mt(table));
}

void *
__nis_remove_item_mt(nis_name name, __nis_hash_table_mt *table) {

    __nis_hash_item_mt  *nl, **pp;
    pthread_t       mtid;

    if (__nis_lock_hash_table(table, 0, "nrimt") == 0)
        return (0);

    /* Find the item, and make sure it's not in use */
    mtid = pthread_self();
    while ((nl = *(pp = __find_item_mt(name, table, (int *)0))) != 0) {
        if (table->destroyItem != 0)
            break;
        if (nl->readers == 0 && nl->writer == 0)
            break;
        if (nl->writer != 0 && nl->writer_id == mtid)
            break;
        (void) pthread_cond_wait(&nl->lock, &table->lock);
    }

    if (nl == 0) {
        (void) __nis_ulock_hash_table(table, 0, "nrimt");
        return (0);
    }

    /* Remove nl from the hash chain */
    *pp = nl->next;
    nl->next = 0;

    /* Remove nl from the linked list of all names */
    if (nl->prv_item)
        nl->prv_item->nxt_item = nl->nxt_item;
    else
        table->first = nl->nxt_item;

    if (nl->nxt_item)
        nl->nxt_item->prv_item = nl->prv_item;
    nl->prv_item = 0;
    nl->nxt_item = 0;

    /* keychain < 0 means not in table anymore */
    nl->keychain = -1;

    /*
     * If this item was locked, we can now decrement the count of
     * locked items for the table.
     */
    if (table->locked_items != 0 &&
        (nl->writer > 0 || nl->readers > 0)) {
        table->locked_items--;
        if (table->locked_items == 0) {
            /* Wake up traversers-to-be */
            (void) pthread_cond_signal(&table->cond);
        }
    }
    (void) pthread_cond_signal(&nl->lock);
    (void) pthread_cond_destroy(&nl->lock);

    /*
     * If the item isn't locked, and an item destructor has been
     * established, invoke the destructor. In that case, we return
     * NULL, so that our caller doesn't try to reference the
     * deleted item.
     */
    if (nl->readers == 0 && nl->writer == 0 && table->destroyItem != 0) {
        (*table->destroyItem)(nl);
        nl = 0;
    }

    (void) __nis_ulock_hash_table(table, 0, "nrimt");

    return (nl);
}

/*
 * Release an item that had been acquired exclusively or non-exclusively.
 * Note that 'readwrite' can assume any integer value, and thus can be
 * used to release any level of recursive locking. It's the responsibility
 * of the caller to make sure that proper nesting is maintained.
 */
int
__nis_release_item(void *arg, __nis_hash_table_mt *table, int readwrite) {

    __nis_hash_item_mt  *item = arg;
    int         wakeup = 0;

    if (item == 0 || __nis_lock_hash_table(table, 0, "nreli") == 0)
        return (0);

    if ((readwrite < 0 && abs(readwrite) > item->writer) ||
        (readwrite < 0 && item->writer > 0 &&
            item->writer_id != pthread_self()) ||
        (readwrite > 0 && readwrite > item->readers)) {
        /* Caller confused; ignore */
        (void) __nis_ulock_hash_table(table, 0, "nreli");
        return (0);
    }

    if (readwrite < 0) {
        item->writer += readwrite;
        if (item->writer == 0 && item->keychain >= 0) {
            if (table->locked_items != 0)
                table->locked_items--;
            wakeup = 1;
        }
    } else if (readwrite > 0) {
        item->readers -= readwrite;
        item->last_reader_id = INV_PTHREAD_ID;
        if (item->readers == 0 && item->keychain >= 0) {
            if (table->locked_items != 0)
                table->locked_items--;
            wakeup = 1;
        }
    }

    if (table->locked_items == 0) {
        /* Wake up traversers-to-be */
        (void) pthread_cond_signal(&table->cond);
    }
    if (wakeup) {
        /* Wake up anyone else who wants this item */
        (void) pthread_cond_signal(&item->lock);
    }

    /*
     * Delete if no references, not linked into list, and destructor
     * established.
     */
    if (item->keychain < 0 &&
            item->readers == 0 && item->writer == 0 &&
            item->next == 0 &&
            item->prv_item == 0 && item->nxt_item == 0 &&
            table->destroyItem != 0)
        (*table->destroyItem)(item);

    (void) __nis_ulock_hash_table(table, 0, "nreli");

    return (1);
}

/*
 * Return -1 if item checked out for both reading and writing, 1 if
 * readonly, and 0 otherwise.
 */
int
__nis_item_access(void *arg) {

    __nis_hash_item_mt  *item = arg;

    if (item != 0) {
        if (item->writer > 0) {
            if (item->writer_id != pthread_self())
                abort();
            return (-1);
        } else if (item->readers > 0) {
            return (1);
        }
    }

    return (0);
}

/*
 * __nis_scan_table_mt()
 *
 * Iterate over all items in a __nis_hash_table_mt. We ignore
 * first/prv_item/nxt_item and scan in hash-chain order.  The iterator
 * function should *not* insert or delete items. If the iterator
 * function returns TRUE the scan terminates. For compatibility with
 * the existing non-MT nis_scan_table() this function has no return
 * value.
 */
void
__nis_scan_table_mt(
    __nis_hash_table_mt *table,
    bool_t      (*func)(__nis_hash_item_mt *, void *),
    void        *funcarg)
{
    int slot;

    if (table == 0) {
        return;
    }

    if (__nis_lock_hash_table(table, 1, "nstmt") == 0) {
        syslog(LOG_DEBUG, "__nis_scan_table_mt: mutex lock failed ");
        return;
    }

    for (slot = 0;
        slot < sizeof (table->keys) / sizeof (table->keys[0]);
        slot++) {
        __nis_hash_item_mt *it;

        for (it = table->keys[slot]; it != 0; it = it->next) {
            if (TRUE == (*func)(it, funcarg)) {
                break;
            }
        }
    }
        if (__nis_ulock_hash_table(table, 1, "nstmt") == 0)
        syslog(LOG_DEBUG, "__nis_scan_table_mt: mutex unlock failed ");
}