/*-
 * Copyright (c) 2014--2019 Taylor R. Campbell
 * All rights reserved.
 *
 * 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 AUTHOR 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 AUTHOR 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/atomic.h>

#include <assert.h>
#include <err.h>
#include <errno.h>
#include <limits.h>
#include <pthread.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

#include "container_of.h"
#include "cradix.h"
#include "ebr.h"

struct ent;

struct map {
	struct cradix_ops	m_cradix_ops;
	struct cradix		m_cradix;
	pthread_mutex_t		m_lock;
	ptrdiff_t		m_keyoff;
	size_t			m_keysz;

	struct {
		pthread_mutex_t		lock;
		pthread_cond_t		cond;
		ebr_t			*ebr;
		struct obj		*objlist;
		struct ent		*nodelist;
		bool			dying;
		void			(*free_cb)(struct ent *);
		pthread_t		thread;
	}			m_gc;
};

struct ent {
	struct cradix_node	ent_node;
	struct ent		*ent_gcnext;
};

struct obj {
	struct obj	*o_gcnext;
	uint8_t		o_data[];
};


static const void *
map_cradix_key(const struct cradix *C, const struct cradix_node *N)
{
	const struct map *const M = container_of(C, struct map, m_cradix);
	const struct ent *const ent = container_of(N, struct ent, ent_node);

	return ((const char *)ent + M->m_keyoff);
}

static void *
map_cradix_alloc(struct cradix *C __unused, size_t size)
{
	struct obj *obj;

	obj = malloc(offsetof(struct obj, o_data[size]));
	if (obj == NULL)
		return NULL;

	return obj->o_data;
}

static void
map_cradix_free(struct cradix *C __unused, void *ptr, size_t size __unused)
{
	struct obj *obj = container_of((uint8_t *)ptr, struct obj, o_data[0]);

	free(obj);
}

static void
map_cradix_recycle(struct cradix *C __unused, void *ptr, size_t size __unused)
{
	struct map *M = container_of(C, struct map, m_cradix);
	struct obj *obj = container_of((uint8_t *)ptr, struct obj, o_data[0]);
	int error;

	error = pthread_mutex_lock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	obj->o_gcnext = M->m_gc.objlist;
	M->m_gc.objlist = obj;

	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}

	error = pthread_mutex_unlock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}
}

struct map_read {
	char mr_dummy;
};

struct map_txn_delete {
	char mtd_dummy;
};

static void *
map_gc_thread(void *cookie)
{
	struct map *M = cookie;
	int error;

	ebr_register(M->m_gc.ebr);
	for (;;) {
		struct obj *obj, *objnext;
		struct ent *node, *nodenext;
		unsigned epoch;

		error = pthread_mutex_lock(&M->m_gc.lock);
		if (error) {
			errno = error;
			err(1, "pthread_mutex_lock");
		}
		while (M->m_gc.objlist == NULL &&
		    M->m_gc.nodelist == NULL &&
		    !M->m_gc.dying) {
			error = pthread_cond_wait(&M->m_gc.cond,
			    &M->m_gc.lock);
			if (error) {
				errno = error;
				err(1, "pthread_cond_wait");
			}
		}
		obj = M->m_gc.objlist;
		M->m_gc.objlist = NULL;
		node = M->m_gc.nodelist;
		M->m_gc.nodelist = NULL;
		error = pthread_mutex_unlock(&M->m_gc.lock);
		if (error) {
			errno = error;
			err(1, "pthread_mutex_unlock");
		}

		/* If there's nothing to do, we're done.  */
		if (obj == NULL && node == NULL) {
			assert(M->m_gc.dying);
			break;
		}

		/* Wait for two epoch transitions.  */
		while (!ebr_sync(M->m_gc.ebr, &epoch))
			continue;
		while (!ebr_sync(M->m_gc.ebr, &epoch))
			continue;

		/* Free them all.  */
		for (; obj != NULL; obj = objnext) {
			objnext = obj->o_gcnext;
			free(obj);
		}
		for (; node != NULL; node = nodenext) {
			nodenext = node->ent_gcnext;
			M->m_gc.free_cb(node);
		}
	}
	ebr_unregister(M->m_gc.ebr);

	return NULL;
}

static void
map_gc_init(struct map *M, void (*free_cb)(struct ent *))
{
	int error;

	error = pthread_mutex_init(&M->m_gc.lock, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_init");
	}
	error = pthread_cond_init(&M->m_gc.cond, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_cond_init");
	}
	if ((M->m_gc.ebr = ebr_create()) == NULL)
		err(1, "ebr_create");
	M->m_gc.objlist = NULL;
	M->m_gc.nodelist = NULL;
	M->m_gc.dying = false;
	M->m_gc.free_cb = free_cb;

	error = pthread_create(&M->m_gc.thread, NULL, &map_gc_thread, M);
	if (error) {
		errno = error;
		err(1, "pthread_create");
	}
}

static void
map_gc_fini(struct map *M)
{
	int error;

	error = pthread_mutex_lock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	M->m_gc.dying = true;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	error = pthread_mutex_unlock(&M->m_gc.lock);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	error = pthread_join(M->m_gc.thread, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_join");
	}
	assert(M->m_gc.objlist == NULL);
	assert(M->m_gc.nodelist == NULL);
}

static void
map_init(struct map *M, ptrdiff_t keyoff, size_t keysz,
    void (*free_cb)(struct ent *))
{
	int error;

	assert(keysz <= UINT_MAX);
	M->m_cradix_ops = (const struct cradix_ops) {
		.keylen = keysz,
		.key = &map_cradix_key,
		.alloc = &map_cradix_alloc,
		.free = &map_cradix_free,
		.recycle = &map_cradix_recycle,
	};

	cradix_init(&M->m_cradix, &M->m_cradix_ops);

	error = pthread_mutex_init(&M->m_lock, NULL);
	if (error) {
		errno = error;
		err(1, "pthread_mutex_init");
	}

	M->m_keyoff = keyoff;
	M->m_keysz = keysz;

	map_gc_init(M, free_cb);
}

static void
map_destroy(struct map *M)
{

	map_gc_fini(M);
	pthread_mutex_destroy(&M->m_lock);
	cradix_destroy(&M->m_cradix);
}

static void
map_register_thread(struct map *M __unused)
{

	ebr_register(M->m_gc.ebr);
}

static void
map_deregister_thread(struct map *M __unused)
{

	ebr_unregister(M->m_gc.ebr);
}

static void
map_read_enter(struct map *M __unused, struct map_read *mr __unused)
{

	ebr_enter(M->m_gc.ebr);
}

static void
map_read_exit(struct map *M __unused, struct map_read *mr __unused)
{

	ebr_exit(M->m_gc.ebr);
}

static struct ent *
map_lookup(struct map *M, const void *key)
{
	struct cradix *C = &M->m_cradix;
	struct cradix_node *N;

	N = cradix_lookup(C, key);
	if (N == NULL)
		return NULL;

	return container_of(N, struct ent, ent_node);
}

static bool
map_insert(struct map *M, const void *key __unused, struct ent *ent)
{
	struct cradix *C = &M->m_cradix;
	struct cradix_node *N = &ent->ent_node;
	struct cradix_node *N0;
	struct cradix_insert insert;
	int error;

	if (!cradix_insert_begin(C, &insert)) {
		errno = ENOMEM;
		err(1, "cradix insert begin");
	}

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	N0 = cradix_insert(C, N, &insert);

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	cradix_insert_end(C, &insert);

	return N0 == N;
}

static struct ent *
map_delete(struct map *M, const void *key)
{
	struct cradix *C = &M->m_cradix;
	struct cradix_node *N;
	struct ent *ent;
	struct cradix_delete delete;
	int error;

	cradix_delete_begin(C, &delete);

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}

	N = cradix_delete_key(C, key, &delete);
#ifdef CRADIX_DEBUG
	cradix_check(C);
#endif

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	cradix_delete_end(C, &delete);

	if (N == NULL)
		return NULL;

	ent = container_of(N, struct ent, ent_node);

	if ((error = pthread_mutex_lock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	ent->ent_gcnext = M->m_gc.nodelist;
	M->m_gc.nodelist = ent;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	if ((error = pthread_mutex_unlock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	return ent;
}

static void
map_txn_delete_begin(struct map *M, struct map_txn_delete *T __unused,
    size_t n __unused)
{
	int error;

	if ((error = pthread_mutex_lock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
}

#include <assert.h>
#include <stdio.h>
static void
map_txn_delete_commit(struct map *M, struct map_txn_delete *T __unused)
{
	int error;

	if ((error = pthread_mutex_unlock(&M->m_lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}
}

static struct ent *
map_txn_delete(struct map *M, const void *key,
    struct map_txn_delete *T __unused)
{
	struct cradix *C = &M->m_cradix;
	struct cradix_node *N;
	struct ent *ent;
	int error;

	N = cradix_delete_key(C, key, NULL);
	if (N == NULL)
		return NULL;

	ent = container_of(N, struct ent, ent_node);

	if ((error = pthread_mutex_lock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_lock");
	}
	ent->ent_gcnext = M->m_gc.nodelist;
	M->m_gc.nodelist = ent;
	error = pthread_cond_broadcast(&M->m_gc.cond);
	if (error) {
		errno = error;
		err(1, "pthread_cond_broadcast");
	}
	if ((error = pthread_mutex_unlock(&M->m_gc.lock)) != 0) {
		errno = error;
		err(1, "pthread_mutex_unlock");
	}

	return ent;
}

#define	MAP_ASYNC	1
#include "stress.i"