/*
 * libfilo - A File Locking Library
 * Alberto Bertogli (albertogli@telpin.com.ar)
 */


#include <sys/types.h>		/* for off_t */
#include <pthread.h>		/* for mutexes */
#include <semaphore.h>		/* for semaphores (duh!) */
#include <stdlib.h>		/* for malloc()/free() */
#include <unistd.h>		/* for lockf() commands */
#include "libfilo.h"


/* We have two lists for each file lock: one of currently locked portions of
 * the file (a portion can have more than one read lock at the same time, but
 * only one write lock), and another one with the current waiters for the
 * lock.
 * FIXME: document this. everything.
 */

#if 0			/* XXX: debug */
#include <stdio.h>
#define printd(...)				\
	do {					\
		fprintf(stderr, "%lu ", pthread_self()); \
		fprintf(stderr, "%s(): ", __FUNCTION__ ); \
		fprintf(stderr, __VA_ARGS__);	\
		fflush(stderr);			\
	} while(0)

void printfl(filock_t *fl)
{
	struct locked_range *lr;
	struct waiter_range *wr;

	fprintf(stderr, "Filock show\n");

	fprintf(stderr, "Locked:\n");
	for (lr = fl->locked; lr != NULL; lr = lr->next) {
		fprintf(stderr, "\t%lu -> %lu (%u) (%lu)\n", lr->start,
				lr->end, lr->mode, lr->owner);
	}

	fprintf(stderr, "Waiter:\n");
	for (wr = fl->waiters; wr != NULL; wr = wr->next) {
		fprintf(stderr, "\t%lu -> %lu (%u) (%lu)\n", wr->start,
				wr->end, wr->mode, wr->owner);
	}
}
#else
	#define printd(...)
	#define printfl(X)
#endif

/* Lock/unlock a filock_t */
#define fl_lock(F) do { pthread_mutex_lock(&(F->lock)); } while (0)
#define fl_unlock(F) do { pthread_mutex_unlock(&(F->lock)); } while (0)


/* Initialize a filock_t structure */
int filo_init(filock_t *fl)
{
	pthread_mutexattr_t attr;
	pthread_mutexattr_init(&attr);
	pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL);
	pthread_mutex_init(&(fl->lock), &attr);
	pthread_mutexattr_destroy(&attr);

	fl->locked = NULL;
	fl->waiters = NULL;
	return 1;
}

/* Frees a filock_t structure */
int filo_free(filock_t *fl)
{
	struct locked_range *lr, *nlr;
	struct waiter_range *wr, *nwr;

	pthread_mutex_destroy(&(fl->lock));

	for (lr = fl->locked; lr != NULL; lr = nlr) {
		nlr = lr->next;
		free(lr);
	}
	fl->locked = NULL;

	for (wr = fl->waiters; wr != NULL; wr = nwr) {
		nwr = wr->next;
		free(wr);
	}
	fl->waiters = NULL;

	return 1;
}

/* Appends a lock to the filock_t */
static void locked_append(filock_t *fl, off_t start, off_t end, int mode,
		pthread_t owner)
{
	struct locked_range *lr;

	lr = malloc(sizeof(struct locked_range));
	lr->start = start;
	lr->end = end;
	lr->mode = mode;
	lr->owner = owner;

	if (fl->locked == NULL) {
		lr->prev = lr->next = NULL;
		fl->locked = lr;
		printd("n: %lu-%lu %d %lu\n", start, end, mode, owner);
	} else {
		lr->prev = NULL;
		fl->locked->prev = lr;
		lr->next = fl->locked;
		fl->locked = lr;
		printd("e: %lu-%lu %d %lu\n", start, end, mode, owner);
	}
}

/* Checks if this thread owns the given locked range */
static int is_ours(struct locked_range *lr)
{
	return !!pthread_equal(lr->owner, pthread_self());
}

/* Checks the given thread owns the given locked range */
static int is_owner(pthread_t owner, struct locked_range *lr)
{
	return !!pthread_equal(lr->owner, owner);
}


/* Checks if the range 1 overlaps with the range 2 */
static int range_overlaps(off_t start1, off_t end1, off_t start2, off_t end2)
{
	if ( (start1 <= start2 && end1 >= end2) ||
			(start1 >= start2 && start1 <= end2) ||
			(end1 >= start2 && end1 <= end2) ) {
		return 1;
	}
	return 0;
}

/* Range overlapping check for locked ranges */
static int lr_range_overlaps(struct locked_range *lr, off_t start, off_t end)
{
	printd("%lu->%lu ov %lu->%lu: %d\n", lr->start, lr->end, start, end, range_overlaps(lr->start, lr->end, start, end));
	return range_overlaps(lr->start, lr->end, start, end);
}

/* Range overlapping check for waiter ranges */
static int wr_range_overlaps(struct waiter_range *wr, off_t start, off_t end)
{
	return range_overlaps(wr->start, wr->end, start, end);
}


/* So far we know:
 *  * there's overlapping between lr and start-end
 *  * we own lr
 * We need to solve the problem by doing:
 *  * If lr is inside start-end, remove it
 *  * If start-end is inside lr, do an "exclude" and break lr in two
 *  * If there's partial overlapping, shrink lr not to step on start-end
 */
static int exclude_range(filock_t *fl, struct locked_range *lr,
		off_t start, off_t end)
{
	printd("exclude %lu->%lu from %lu->%lu\n", start, end, lr->start, lr->end);
	if (lr->start >= start && lr->end <= end) {
		/* it's equal or contained inside, tell to remove */
		return 0;
	} else if (lr->start < start && lr->end <= end) {
		/* we're overlapping from the left, shrink it */
		printd("shrink end from %lu to %lu\n", lr->end, start - 1);
		lr->end = start - 1;
		return 1;
	} else if (lr->start >= start && lr->end > end) {
		/* we're overlapping from the right, shrink it */
		printd("shrink start %lu to %lu\n", lr->start, end + 1);
		lr->start = end + 1;
		return 1;
	} else if (lr->start < start && lr->end > end) {
		/* start-end is contained inside lr, we need to split lr */
		locked_append(fl, lr->start, start - 1, lr->mode,
				pthread_self());
		locked_append(fl, end + 1, lr->end, lr->mode, pthread_self());
		/* tell the caller to remove lr */
		return 0;
	}

	/* we should NEVER enter here, since all the cases should have been
	 * covered */
	return 1;
}


/* Checks if the given thread can lock the given region */
static int can_lock_tid(filock_t *fl, off_t start, off_t end, int mode,
		pthread_t owner)
{
	struct locked_range *lr;

	for (lr = fl->locked; lr != NULL; lr = lr->next) {
		/* if we are inside, contained or overlapping somebody else,
		 * check if:
		 *  * is ours, so we can play with it freely
		 *  * is a write lock and we try to read, can't get it
		 *  * we try to write, can't get it
		 */
		if (lr_range_overlaps(lr, start, end)) {
			if (is_owner(owner, lr)) {
				/* this check could be moved before the long
				 * "if" above, but it's an unlikely case and
				 * the test could get expensive */
				continue;
			}
			if (mode == FL_WR_MODE || lr->mode == FL_WR_MODE) {
				return 0;
			}
		}
	}
	printd("can lock it from %lu to %lu as %d\n", start, end, mode);
	return 1;
}

/* As can_lock_tid() but gets the owner from the current thread */
static int can_lock(filock_t *fl, off_t start, off_t end, int mode)
{
	return can_lock_tid(fl, start, end, mode, pthread_self());
}


/* Lock a given region, assuming that is not free and we're allowed to own it
 * (these checks are performed by the caller) */
static int do_lock_tid(filock_t *fl, off_t start, off_t end, int mode,
		pthread_t owner)
{
	struct locked_range *lr, *next;

	for (lr = fl->locked; lr != NULL; lr = next) {
		next = lr->next;

		if (!is_ours(lr))
			continue;
		if (!lr_range_overlaps(lr, start, end))
			continue;

		printd("overlap %lu %lu %d %lu\n", start, end, mode, owner);
		if (exclude_range(fl, lr, start, end) == 0) {
			printd("rem lr %lu->%lu\n", lr->start, lr->end);
			/* we need to remove lr */
			if (fl->locked == lr)
				fl->locked = lr->next;
			if (lr->prev != NULL)
				lr->prev->next = lr->next;
			if (lr->next != NULL)
				lr->next->prev = lr->prev;
			free(lr);
		}
	}

	/* now the region is safe to do this */
	locked_append(fl, start, end, mode, owner);
	return 1;
}


/* Same as do_lock_tid(), but gets the tid from the currently running thread;
 * it's a shortcut for a lot of uses */
static int do_lock(filock_t *fl, off_t start, off_t end, int mode)
{
	return do_lock_tid(fl, start, end, mode, pthread_self());
}


/* Check if a region is free from locks so we can add the lock right in,
 * skipping all the other tests */
static int region_free(filock_t *fl, off_t start, off_t end) {
	struct locked_range *lr;
	for (lr = fl->locked; lr != NULL; lr = lr->next) {
		if (lr_range_overlaps(lr, start, end))
			return 0;
	}
	return 1;
}

/* Tries to get a lock, returns 1 if success or 0 if failure */
int filo_trylock(filock_t *fl, off_t start, off_t len, int mode)
{
	int rv = 0;
	off_t end = start + len - 1;

	if (len <= 0)
		return 0;

	fl_lock(fl);

	/* fast path for the uncontended case */
	if (fl->locked == NULL) {
		locked_append(fl, start, end, mode, pthread_self());
		rv = 1;
	} else if (region_free(fl, start, end)) {
		locked_append(fl, start, end, mode, pthread_self());
		rv = 1;
	} else if (can_lock(fl, start, end, mode)) {
		do_lock(fl, start, end, mode);
		rv = 1;
	} else {
		/* the region is busy, we would lock */
		rv = 0;
	}

	fl_unlock(fl);
	return rv;
}


static void wait_on(filock_t *fl, off_t start, off_t end, int mode)
{
	/* all waiter_ranges are created and destroyed here. A wr is born
	 * here, go to bed in the locking below, until wake_up() wakes us up
	 * and he dies. While it is manipulated several times outside this
	 * function, here is the only place where it's actually modified; it
	 * used to be allocated directly on the stack, but maybe some stuff
	 * assume thread stack is not touched by other threads and it could
	 * cause some problems in the future; remember: "better safe than
	 * sorry". */
	struct waiter_range *wr;
	wr = malloc(sizeof(struct waiter_range));

	/* initialize wr */
	wr->start = start;
	wr->end = end;
	wr->mode = mode;
	wr->owner = pthread_self();
	wr->next = NULL;
	wr->prev = NULL;

	sem_init(&(wr->sem), 0, 0);

	/* add to the semi-circular list */
	if (fl->waiters == NULL) {
		wr->next = NULL;
		wr->prev = wr;
		fl->waiters = wr;
	} else {
		wr->next = NULL;
		wr->prev = fl->waiters->prev;
		fl->waiters->prev->next = wr;
		fl->waiters->prev = wr;
	}

	fl_unlock(fl);

	/* block until some other thread wakes us up */
	while (sem_wait(&(wr->sem)) != 0)
		/* it can fail with EINTR, retry */
		;

	free(wr);
}

static void wake_up(filock_t *fl, off_t start, off_t end)
{
	struct waiter_range *wr;

	for (wr = fl->waiters; wr != NULL; wr = wr->next) {
		if (!wr_range_overlaps(wr, start, end))
			/* if the region doesn't overlap, we know beforehand
			 * the status couldn't have changed */
			continue;
		if (can_lock_tid(fl, wr->start, wr->end, wr->mode, wr->owner)) {
			do_lock_tid(fl, wr->start, wr->end, wr->mode,
					wr->owner);

			/* remove from the semi-circular list */
			if (fl->waiters == wr) {
				/* head */
				if (wr->next != NULL)
					wr->next->prev = fl->waiters->prev;
				fl->waiters = wr->next;
			} else if (fl->waiters->prev == wr) {
				/* tail */
				wr->prev->next = NULL;
				fl->waiters->prev = wr->prev;
			} else {
				/* middle */
				wr->prev->next = wr->next;
				wr->next->prev = wr->prev;
			}

			/* this will wake the thread up, which is blocked in
			 * wait_on(), and it will then free wr */
			sem_post(&(wr->sem));

			return;
		}
	}

	/* nobody was waiting! */
	return;
}


/* Get a lock, blocking until available */
int filo_lock(filock_t *fl, off_t start, off_t len, int mode)
{
	off_t end = start + len - 1;

	if (len <= 0)
		return 0;

	fl_lock(fl);

	/* fast path for the uncontended case */
	if (fl->locked == NULL) {
		locked_append(fl, start, end, mode, pthread_self());
		fl_unlock(fl);
	} else if (region_free(fl, start, end)) {
		locked_append(fl, start, end, mode, pthread_self());
		fl_unlock(fl);
	} else if (can_lock(fl, start, end, mode)) {
		printd("locking\n");
		do_lock(fl, start, end, mode);
		fl_unlock(fl);
	} else {
		/* the region is busy, we wait */
		wait_on(fl, start, end, mode);
		/* when we return, fl->lock has already been unlocked, there's
		 * no need to release it */
	}

	printfl(fl);
	return 1;
}


int filo_unlock(filock_t *fl, off_t start, off_t len)
{
	struct locked_range *lr, *next;
	off_t end = start + len - 1;

	if (len <= 0)
		return 0;

	fl_lock(fl);

	for (lr = fl->locked; lr != NULL; lr = next) {
		next = lr->next;

		if (!is_ours(lr))
			continue;
		if (!lr_range_overlaps(lr, start, end))
			continue;

		/* the range is ours and overlaps, unlock this area */
		if (exclude_range(fl, lr, start, end) == 0) {
			/* we need to remove lr */
			if (fl->locked == lr)
				fl->locked = lr->next;
			if (lr->prev != NULL)
				lr->prev->next = lr->next;
			if (lr->next != NULL)
				lr->next->prev = lr->prev;
			free(lr);
		}
	}

	wake_up(fl, start, end);
	printd("UNLOCKED\n");
	printfl(fl);
	fl_unlock(fl);
	return 1;
}


int filo_plockf(filock_t *fl, int cmd, off_t start, off_t len)
{
	int rv, mode = 0;
	off_t end = start + len - 1;

	if (len <= 0)
		return 0;

	if (cmd & _FL_READ)
		mode = FL_RD_MODE;
	else if (cmd & _FL_WRITE)
		mode = FL_WR_MODE;

	if (cmd & _FL_LOCK)
		rv = filo_lock(fl, start, len, mode);
	else if (cmd & _FL_TLOCK)
		rv = filo_trylock(fl, start, len, mode);
	else if (cmd & _FL_ULOCK)
		rv = filo_unlock(fl, start, end);
	else
		return -1;

	if (rv == 0)
		return -1;
	return 0;
}