/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "primpl.h"

#include <string.h>

#if defined(HPUX) && defined(_PR_PTHREADS)

#include <pthread.h>
#define HAVE_UNIX98_RWLOCK
#define RWLOCK_T pthread_rwlock_t
#define RWLOCK_INIT(lock) pthread_rwlock_init(lock, NULL)
#define RWLOCK_DESTROY(lock) pthread_rwlock_destroy(lock)
#define RWLOCK_RDLOCK(lock) pthread_rwlock_rdlock(lock)
#define RWLOCK_WRLOCK(lock) pthread_rwlock_wrlock(lock)
#define RWLOCK_UNLOCK(lock) pthread_rwlock_unlock(lock)

#elif defined(SOLARIS) && (defined(_PR_PTHREADS) \
        || defined(_PR_GLOBAL_THREADS_ONLY))

#include <synch.h>
#define HAVE_UI_RWLOCK
#define RWLOCK_T rwlock_t
#define RWLOCK_INIT(lock) rwlock_init(lock, USYNC_THREAD, NULL)
#define RWLOCK_DESTROY(lock) rwlock_destroy(lock)
#define RWLOCK_RDLOCK(lock) rw_rdlock(lock)
#define RWLOCK_WRLOCK(lock) rw_wrlock(lock)
#define RWLOCK_UNLOCK(lock) rw_unlock(lock)

#endif

/*
 * Reader-writer lock
 */
struct PRRWLock {
	char			*rw_name;			/* lock name					*/
	PRUint32		rw_rank;			/* rank of the lock				*/

#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	RWLOCK_T		rw_lock;
#else
    PRLock			*rw_lock;
	PRInt32			rw_lock_cnt;		/* ==  0, if unlocked			*/
										/* == -1, if write-locked		*/
										/* > 0	, # of read locks		*/
	PRUint32		rw_reader_cnt;		/* number of waiting readers	*/
	PRUint32		rw_writer_cnt;		/* number of waiting writers	*/
	PRCondVar   	*rw_reader_waitq;	/* cvar for readers 			*/
	PRCondVar   	*rw_writer_waitq;	/* cvar for writers				*/
#ifdef DEBUG
    PRThread 		*rw_owner;			/* lock owner for write-lock	*/
#endif
#endif
};

#ifdef DEBUG
#define _PR_RWLOCK_RANK_ORDER_DEBUG	/* enable deadlock detection using
									   rank-order for locks
									*/
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG

static PRUintn	pr_thread_rwlock_key;			/* TPD key for lock stack */
static PRUintn	pr_thread_rwlock_alloc_failed;

#define	_PR_RWLOCK_RANK_ORDER_LIMIT	10

typedef struct thread_rwlock_stack {
	PRInt32		trs_index;									/* top of stack */
	PRRWLock	*trs_stack[_PR_RWLOCK_RANK_ORDER_LIMIT];	/* stack of lock
														 	   pointers */

} thread_rwlock_stack;

static void _PR_SET_THREAD_RWLOCK_RANK(PRRWLock *rwlock);
static PRUint32 _PR_GET_THREAD_RWLOCK_RANK(void);
static void _PR_UNSET_THREAD_RWLOCK_RANK(PRRWLock *rwlock);
static void _PR_RELEASE_LOCK_STACK(void *lock_stack);

#endif

/*
 * Reader/Writer Locks
 */

/*
 * PR_NewRWLock
 *		Create a reader-writer lock, with the given lock rank and lock name
 *	
 */

PR_IMPLEMENT(PRRWLock *)
PR_NewRWLock(PRUint32 lock_rank, const char *lock_name)
{
    PRRWLock *rwlock;
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	int err;
#endif

    if (!_pr_initialized) _PR_ImplicitInitialization();

    rwlock = PR_NEWZAP(PRRWLock);
    if (rwlock == NULL)
		return NULL;

	rwlock->rw_rank = lock_rank;
	if (lock_name != NULL) {
		rwlock->rw_name = (char*) PR_Malloc(strlen(lock_name) + 1);
    	if (rwlock->rw_name == NULL) {
			PR_DELETE(rwlock);
			return(NULL);
		}
		strcpy(rwlock->rw_name, lock_name);
	} else {
		rwlock->rw_name = NULL;
	}
	
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	err = RWLOCK_INIT(&rwlock->rw_lock);
	if (err != 0) {
		PR_SetError(PR_UNKNOWN_ERROR, err);
		PR_Free(rwlock->rw_name);
		PR_DELETE(rwlock);
		return NULL;
	}
	return rwlock;
#else
	rwlock->rw_lock = PR_NewLock();
    if (rwlock->rw_lock == NULL) {
		goto failed;
	}
	rwlock->rw_reader_waitq = PR_NewCondVar(rwlock->rw_lock);
    if (rwlock->rw_reader_waitq == NULL) {
		goto failed;
	}
	rwlock->rw_writer_waitq = PR_NewCondVar(rwlock->rw_lock);
    if (rwlock->rw_writer_waitq == NULL) {
		goto failed;
	}
	rwlock->rw_reader_cnt = 0;
	rwlock->rw_writer_cnt = 0;
	rwlock->rw_lock_cnt = 0;
	return rwlock;

failed:
	if (rwlock->rw_reader_waitq != NULL) {
		PR_DestroyCondVar(rwlock->rw_reader_waitq);	
	}
	if (rwlock->rw_lock != NULL) {
		PR_DestroyLock(rwlock->rw_lock);
	}
	PR_Free(rwlock->rw_name);
	PR_DELETE(rwlock);
	return NULL;
#endif
}

/*
** Destroy the given RWLock "lock".
*/
PR_IMPLEMENT(void)
PR_DestroyRWLock(PRRWLock *rwlock)
{
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	int err;
	err = RWLOCK_DESTROY(&rwlock->rw_lock);
	PR_ASSERT(err == 0);
#else
	PR_ASSERT(rwlock->rw_reader_cnt == 0);
	PR_DestroyCondVar(rwlock->rw_reader_waitq);	
	PR_DestroyCondVar(rwlock->rw_writer_waitq);	
	PR_DestroyLock(rwlock->rw_lock);
#endif
	if (rwlock->rw_name != NULL)
		PR_Free(rwlock->rw_name);
    PR_DELETE(rwlock);
}

/*
** Read-lock the RWLock.
*/
PR_IMPLEMENT(void)
PR_RWLock_Rlock(PRRWLock *rwlock)
{
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
int err;
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG
	/*
	 * assert that rank ordering is not violated; the rank of 'rwlock' should
	 * be equal to or greater than the highest rank of all the locks held by
	 * the thread.
	 */
	PR_ASSERT((rwlock->rw_rank == PR_RWLOCK_RANK_NONE) || 
					(rwlock->rw_rank >= _PR_GET_THREAD_RWLOCK_RANK()));
#endif

#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	err = RWLOCK_RDLOCK(&rwlock->rw_lock);
	PR_ASSERT(err == 0);
#else
	PR_Lock(rwlock->rw_lock);
	/*
	 * wait if write-locked or if a writer is waiting; preference for writers
	 */
	while ((rwlock->rw_lock_cnt < 0) ||
			(rwlock->rw_writer_cnt > 0)) {
		rwlock->rw_reader_cnt++;
		PR_WaitCondVar(rwlock->rw_reader_waitq, PR_INTERVAL_NO_TIMEOUT);
		rwlock->rw_reader_cnt--;
	}
	/*
	 * Increment read-lock count
	 */
	rwlock->rw_lock_cnt++;

	PR_Unlock(rwlock->rw_lock);
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG
	/*
	 * update thread's lock rank
	 */
	if (rwlock->rw_rank != PR_RWLOCK_RANK_NONE)
		_PR_SET_THREAD_RWLOCK_RANK(rwlock);
#endif
}

/*
** Write-lock the RWLock.
*/
PR_IMPLEMENT(void)
PR_RWLock_Wlock(PRRWLock *rwlock)
{
#if defined(DEBUG)
PRThread *me = PR_GetCurrentThread();
#endif
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
int err;
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG
	/*
	 * assert that rank ordering is not violated; the rank of 'rwlock' should
	 * be equal to or greater than the highest rank of all the locks held by
	 * the thread.
	 */
	PR_ASSERT((rwlock->rw_rank == PR_RWLOCK_RANK_NONE) || 
					(rwlock->rw_rank >= _PR_GET_THREAD_RWLOCK_RANK()));
#endif

#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	err = RWLOCK_WRLOCK(&rwlock->rw_lock);
	PR_ASSERT(err == 0);
#else
	PR_Lock(rwlock->rw_lock);
	/*
	 * wait if read locked
	 */
	while (rwlock->rw_lock_cnt != 0) {
		rwlock->rw_writer_cnt++;
		PR_WaitCondVar(rwlock->rw_writer_waitq, PR_INTERVAL_NO_TIMEOUT);
		rwlock->rw_writer_cnt--;
	}
	/*
	 * apply write lock
	 */
	rwlock->rw_lock_cnt--;
	PR_ASSERT(rwlock->rw_lock_cnt == -1);
#ifdef DEBUG
	PR_ASSERT(me != NULL);
	rwlock->rw_owner = me;
#endif
	PR_Unlock(rwlock->rw_lock);
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG
	/*
	 * update thread's lock rank
	 */
	if (rwlock->rw_rank != PR_RWLOCK_RANK_NONE)
		_PR_SET_THREAD_RWLOCK_RANK(rwlock);
#endif
}

/*
** Unlock the RW lock.
*/
PR_IMPLEMENT(void)
PR_RWLock_Unlock(PRRWLock *rwlock)
{
#if defined(DEBUG)
PRThread *me = PR_GetCurrentThread();
#endif
#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
int err;
#endif

#if defined(HAVE_UNIX98_RWLOCK) || defined(HAVE_UI_RWLOCK)
	err = RWLOCK_UNLOCK(&rwlock->rw_lock);
	PR_ASSERT(err == 0);
#else
	PR_Lock(rwlock->rw_lock);
	/*
	 * lock must be read or write-locked
	 */
	PR_ASSERT(rwlock->rw_lock_cnt != 0);
	if (rwlock->rw_lock_cnt > 0) {

		/*
		 * decrement read-lock count
		 */
		rwlock->rw_lock_cnt--;
		if (rwlock->rw_lock_cnt == 0) {
			/*
			 * lock is not read-locked anymore; wakeup a waiting writer
			 */
			if (rwlock->rw_writer_cnt > 0)
				PR_NotifyCondVar(rwlock->rw_writer_waitq);
		}
	} else {
		PR_ASSERT(rwlock->rw_lock_cnt == -1);

		rwlock->rw_lock_cnt = 0;
#ifdef DEBUG
    	PR_ASSERT(rwlock->rw_owner == me);
    	rwlock->rw_owner = NULL;
#endif
		/*
		 * wakeup a writer, if present; preference for writers
		 */
		if (rwlock->rw_writer_cnt > 0)
			PR_NotifyCondVar(rwlock->rw_writer_waitq);
		/*
		 * else, wakeup all readers, if any
		 */
		else if (rwlock->rw_reader_cnt > 0)
			PR_NotifyAllCondVar(rwlock->rw_reader_waitq);
	}
	PR_Unlock(rwlock->rw_lock);
#endif

#ifdef _PR_RWLOCK_RANK_ORDER_DEBUG
	/*
	 * update thread's lock rank
	 */
	if (rwlock->rw_rank != PR_RWLOCK_RANK_NONE)
		_PR_UNSET_THREAD_RWLOCK_RANK(rwlock);
#endif
	return;
}

#ifndef _PR_RWLOCK_RANK_ORDER_DEBUG

void _PR_InitRWLocks(void) { }

#else

void _PR_InitRWLocks(void)
{
	/*
	 * allocated thread-private-data index for rwlock list
	 */
	if (PR_NewThreadPrivateIndex(&pr_thread_rwlock_key,
			_PR_RELEASE_LOCK_STACK) == PR_FAILURE) {
		pr_thread_rwlock_alloc_failed = 1;
		return;
	}
}

/*
 * _PR_SET_THREAD_RWLOCK_RANK
 *		Set a thread's lock rank, which is the highest of the ranks of all
 *		the locks held by the thread. Pointers to the locks are added to a
 *		per-thread list, which is anchored off a thread-private data key.
 */

static void
_PR_SET_THREAD_RWLOCK_RANK(PRRWLock *rwlock)
{
thread_rwlock_stack *lock_stack;
PRStatus rv;

	/*
	 * allocate a lock stack
	 */
	if ((lock_stack = PR_GetThreadPrivate(pr_thread_rwlock_key)) == NULL) {
		lock_stack = (thread_rwlock_stack *)
						PR_CALLOC(1 * sizeof(thread_rwlock_stack));
		if (lock_stack) {
			rv = PR_SetThreadPrivate(pr_thread_rwlock_key, lock_stack);
			if (rv == PR_FAILURE) {
				PR_DELETE(lock_stack);
				pr_thread_rwlock_alloc_failed = 1;
				return;
			}
		} else {
			pr_thread_rwlock_alloc_failed = 1;
			return;
		}
	}
	/*
	 * add rwlock to lock stack, if limit is not exceeded
	 */
	if (lock_stack) {
		if (lock_stack->trs_index < _PR_RWLOCK_RANK_ORDER_LIMIT)
			lock_stack->trs_stack[lock_stack->trs_index++] = rwlock;	
	}
}

static void
_PR_RELEASE_LOCK_STACK(void *lock_stack)
{
	PR_ASSERT(lock_stack);
	PR_DELETE(lock_stack);
}

/*
 * _PR_GET_THREAD_RWLOCK_RANK
 *
 *		return thread's lock rank. If thread-private-data for the lock
 *		stack is not allocated, return PR_RWLOCK_RANK_NONE.
 */
	
static PRUint32
_PR_GET_THREAD_RWLOCK_RANK(void)
{
	thread_rwlock_stack *lock_stack;

	lock_stack = PR_GetThreadPrivate(pr_thread_rwlock_key);
	if (lock_stack == NULL || lock_stack->trs_index == 0)
		return (PR_RWLOCK_RANK_NONE);
	else
		return(lock_stack->trs_stack[lock_stack->trs_index - 1]->rw_rank);
}

/*
 * _PR_UNSET_THREAD_RWLOCK_RANK
 *
 *		remove the rwlock from the lock stack. Since locks may not be
 *		unlocked in a FIFO order, the entire lock stack is searched.
 */
	
static void
_PR_UNSET_THREAD_RWLOCK_RANK(PRRWLock *rwlock)
{
	thread_rwlock_stack *lock_stack;
	int new_index = 0, index, done = 0;

	lock_stack = PR_GetThreadPrivate(pr_thread_rwlock_key);

	PR_ASSERT(lock_stack != NULL);

	for (index = lock_stack->trs_index - 1; index >= 0; index--) {
		if (!done && (lock_stack->trs_stack[index] == rwlock))  {
			/*
			 * reset the slot for rwlock
			 */
			lock_stack->trs_stack[index] = NULL;
			done = 1;
		}
		/*
		 * search for the lowest-numbered empty slot, above which there are
		 * no non-empty slots
		 */
		if (!new_index && (lock_stack->trs_stack[index] != NULL))
			new_index = index + 1;
		if (done && new_index)
			break;
	}
	/*
	 * set top of stack to highest numbered empty slot
	 */
	lock_stack->trs_index = new_index;

}

#endif 	/* _PR_RWLOCK_RANK_ORDER_DEBUG */