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