/*	$NetBSD$	*/

/*
 * XXX WARNING WARNING WARNING XXX
 *
 * This code does not run!  I have not even compile-tested it.
 *
 * prwlock: Pserialized reader/writer lock.  The writer lock is very
 * expensive, but frequent readers do not require interprocessor
 * synchronization.  (Infrequent readers will likely incur the
 * interprocessor synchronization, defeating the purpose.)
 *
 * Prwlocks are not recursive.  Under DIAGNOSTIC, prwlock_writer_enter
 * checks to ensure you do not recursively acquire a writer lock.
 * Under DEBUG, prwlock_reader_enter checks to ensure you do not
 * recursively acquire a reader lock, at the cost of scalability.
 */

/*-
 * Copyright (c) 2014 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Taylor R. Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD$");

#include <sys/types.h>
#include <sys/condvar.h>
#include <sys/lwp.h>
#include <sys/mutex.h>
#include <sys/pool.h>
#include <sys/pserialize.h>
#include <sys/queue.h>

struct prwlock {
	kmutex_t		prwl_lock;
	kcondvar_t		prwl_cv;
	LIST_HEAD(, prw_reader)	prwl_readers;
	struct lwp		*prwl_writer;
	pserialize_t		prwl_psz;
	pool_cache_t		prwl_reader_pc;
#if DIAGNOSTIC || DEBUG
	const char		*prwl_name;
#endif
};

struct prw_reader {
	LIST_ENTRY(prw_reader)	pr_entry;
	struct lwp		*pr_reader;
};

struct prw_writer;		/* fictitious */

static pool_cache_t prwlock_pc;

int
prwlocks_init(void)
{

	prwlock_pc = pool_cache_init(sizeof(struct prwlock), 0, 0, 0,
	    "prwlock", NULL, IPL_NONE, NULL, NULL, NULL);
}

struct prwlock *
prwlock_create(const char *name)
{
	struct prwlock *const prwlock = pool_cache_get(prwlock_pc, PR_WAITOK);

	mutex_init(&prwlock->prwl_lock, MUTEX_DEFAULT, IPL_NONE);
	cv_init(&prwlock->prwl_cv, name);
	LIST_INIT(&prwlock->prwl_readers);
	prwlock->prwl_writer = NULL;
	prwlock->prwl_psz = pserialize_create();
	prwlock->prwl_reader_pc = pool_cache_init(sizeof(struct prw_reader),
	    0, 0, 0, "prw_reader", NULL, IPL_NONE,
	    &prw_reader_ctor, &prw_reader_dtor, prwlock);
#if DIAGNOSTIC || DEBUG
	prwlock->prwl_name = name;
#endif

	return prwlock;
}

void
prwlock_destroy(struct prwlock *prwlock)
{

	pool_cache_destroy(prwlock->prwl_reader_pc);
	pserialize_destroy(prwlock->prwl_psz);
	KASSERTMSG((prwlock->prwl_writer == NULL),
	    "prwlock %s @ %p writer-locked by lwp %p",
	    prwlock->prwl_name, prwlock, prwlock->prwl_writer);
	KASSERTMSG(LIST_EMPTY(&prwlock->prwl_readers),
	    "prwlock %s @ %p reader-locked",
	    prwlock->prwl_name, prwlock);
	cv_destroy(&prwlock->prwl_cv);
	mutex_destroy(&prwlock->prwl_lock);

	pool_cache_put(prwlock_pc, prwlock);
}

static int
prw_reader_ctor(void *vprwlock, void *vreader, int flags __unused)
{
	struct prwlock *const prwlock = vprwlock;
	struct prw_reader *const reader = vreader;

	reader->pr_reader = NULL;

	mutex_enter(&prwlock->prwl_lock);
	LIST_INSERT_TAIL(&prwlock->prwl_readers, reader);
	mutex_exit(&prwlock->prwl_lock);

	return 0;
}

static void
prw_reader_dtor(void *vprwlock, void *vreader)
{
	struct prwlock *const prwlock = vprwlock;
	struct prw_reader *const reader = vreader;

	KASSERTMSG((reader->pr_reader == NULL),
	    "prwlock %s @ %p reader %p still in use by lwp %p",
	    prwlock->prwl_name, prwlock, reader, reader->pr_reader);

	mutex_enter(&prwlock->prwl_lock);
	LIST_REMOVE(reader, pr_entry);
	mutex_exit(&prwlock->prwl_lock);
}

#if DEBUG
static bool
prw_reader_p(struct prwlock *prwlock)
{
	struct prw_reader *reader;

	mutex_enter(&prwlock->prwl_lock);
	LIST_FOREACH(reader, &prwlock->prwl_readers, pr_entry) {
		if (reader->pr_reader == curlwp)
			break;
	}
	mutex_exit(&prwlock->prwl_lock);

	return (reader != NULL);
}
#endif

void
prwlock_reader_enter(struct prwlock *prwlock, struct prw_reader **readerp)
{
	struct prw_reader *reader;
	int s;

	KDASSERTMSG(!prw_reader_p(prwlock),
	    "read-locking against myself: prwlock %s @ %p, lwp %p",
	    prwlock->prwl_name, prwlock, curlwp);

	reader = pool_cache_get(prwlock->prwl_reader_pc, PR_WAITOK);
	KASSERT(reader != NULL);

	s = pserialize_read_enter();
	if (__predict_false(prwlock->prwl_writer != NULL)) {
		pserialize_read_exit(s);
		mutex_enter(&prwlock->prwl_lock);
		while (prwlock->prwl_writer != NULL)
			cv_wait(&prwlock->prwl_cv, &prwlock->prwl_lock);
		reader->pr_reader = curlwp;
		mutex_exit(&prwlock->prwl_lock);
		goto out;
	}
	reader->pr_reader = curlwp;
	pserialize_read_exit(s);

out:	*readerp = reader;
}

void
prwlock_reader_exit(struct prwlock *prwlock, struct prw_reader *reader)
{
	int s;

	KASSERT(reader != NULL);
	KASSERTMSG((reader->pr_reader == curlwp),
	    "prwlock %s @ %p reader %p switched lwp from %p to %p",
	    prwlock->prwl_name, prwlock, reader, reader->pr_reader, curlwp);

	s = pserialize_read_enter();
	if (__predict_false(prwlock->prwl_writer != NULL)) {
		pserialize_read_exit(s);
		mutex_enter(&prwlock->prwl_lock);
		reader->pr_reader = NULL;
		cv_broadcast(&prwlock->prwl_cv);
		mutex_exit(&prwlock->prwl_lock);
		goto out;
	}
	reader->pr_reader = NULL;
	pserialize_read_exit(s);

out:	pool_cache_put(prwlock->prwl_reader_pc, reader);
}

static bool
prwlock_readers_p(struct prwlock *prwlock)
{
	struct prw_reader *reader;

	KASSERT(mutex_owned(&prwlock->prwl_lock));

	LIST_FOREACH(reader, &prwlock->prwl_readers, pr_entry) {
		if (reader->pr_reader != NULL)
			return true;
	}

	return false;
}

void
prwlock_writer_enter(struct prwlock *prwlock, struct prw_writer **writerp)
{

	mutex_enter(&prwlock->prwl_lock);
	KASSERTMSG((prwlock->prwl_writer != curlwp),
	    "write-locking against myself: prwlock %s @ %p, lwp %p",
	    prwlock->prwl_name, prwlock, curlwp);
	while (prwlock->prwl_writer != NULL)
		cv_wait(&prwlock->prwl_cv, &prwlock->prwl_lock);
	prwlock->prwl_writer = curlwp;
	pserialize_perform(prwlock->prwl_psz);
	while (prwlock_readers_p(prwlock))
		cv_wait(&prwlock->prwl_cv, &prwlock->prwl_lock);
	mutex_exit(&prwlock->prwl_lock);

	*writerp = (struct prw_writer *)prwlock;
}

void
prwlock_writer_exit(struct prwlock *prwlock, struct prw_writer *writer)
{

	KASSERT(writer == (struct rrw_writer *)prwlock);

	mutex_enter(&prwlock->prwl_lock);
	KASSERTMSG((prwlock->prwl_writer == curlwp),
	    "lwp %p writer-unlocking prwlock %s @ %p held by lwp %p",
	    curlwp, prwlock->prwl_name, prwlock, prwlock->prwl_writer);
	prwlock->prwl_writer = NULL;
	cv_broadcast(&prwlock->prwl_cv);
	mutex_exit(&prwlock->prwl_lock);
}