8322 nl: misleading-indentation

[unleashed/tickless.git] / usr / src / lib / libnisdb / nis_hashitem.c

/*
 * 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 2005 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 *)) {

        int     errorcode;

        if (table != 0) {
                errorcode = pthread_mutex_init(&table->lock, 0);
                if (errorcode != 0) {
                        syslog(LOG_WARNING, "__nis_init_hash_table: "
                            "(table->lock) pthread_mutex_init returned %d (%s)",
                            errorcode, strerror(errorcode));
                }

                errorcode = pthread_cond_init(&table->cond, 0);
                if (errorcode != 0) {
                        syslog(LOG_WARNING, "__nis_init_hash_table: "
                            "(table->cond) pthread_cond_init returned %d (%s)",
                            errorcode, strerror(errorcode));
                }

                errorcode = pthread_mutex_init(&table->traverser_id_lock, 0);
                if (errorcode != 0) {
                        syslog(LOG_WARNING, "__nis_init_hash_table: "
                            "(table->traverser_id_lock) "
                            "pthread_mutex_init returned %d (%s)",
                            errorcode, strerror(errorcode));
                }

                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 ");
}