/*
 * Copyright (c) 2006 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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.
 */

/** @addtogroup libc
 * @{
 */
/** @file
 */

#ifndef _LIBC_FUTEX_H_
#define _LIBC_FUTEX_H_

#include <assert.h>
#include <stdatomic.h>
#include <errno.h>
#include <libc.h>
#include <time.h>
#include <fibril.h>
#include <abi/cap.h>
#include <abi/synch.h>

typedef struct futex {
	volatile atomic_int val;
	volatile cap_waitq_handle_t whandle;

#ifdef CONFIG_DEBUG_FUTEX
	_Atomic(fibril_t *) owner;
#endif
} futex_t;

extern errno_t futex_initialize(futex_t *futex, int value);

static inline errno_t futex_destroy(futex_t *futex)
{
	if (futex->whandle) {
		errno_t rc;
		rc = __SYSCALL1(SYS_WAITQ_DESTROY, (sysarg_t) futex->whandle);
		futex->whandle = CAP_NIL;
		return rc;
	}
	return EOK;
}

#ifdef CONFIG_DEBUG_FUTEX

void __futex_assert_is_locked(futex_t *, const char *);
void __futex_assert_is_not_locked(futex_t *, const char *);
void __futex_lock(futex_t *, const char *);
void __futex_unlock(futex_t *, const char *);
bool __futex_trylock(futex_t *, const char *);
void __futex_give_to(futex_t *, void *, const char *);

#define futex_lock(futex) __futex_lock((futex), #futex)
#define futex_unlock(futex) __futex_unlock((futex), #futex)
#define futex_trylock(futex) __futex_trylock((futex), #futex)

#define futex_give_to(futex, new_owner) __futex_give_to((futex), (new_owner), #futex)
#define futex_assert_is_locked(futex) __futex_assert_is_locked((futex), #futex)
#define futex_assert_is_not_locked(futex) __futex_assert_is_not_locked((futex), #futex)

#else

#define futex_lock(fut)     (void) futex_down((fut))
#define futex_trylock(fut)  futex_trydown((fut))
#define futex_unlock(fut)   (void) futex_up((fut))

#define futex_give_to(fut, owner) ((void)0)
#define futex_assert_is_locked(fut) assert(atomic_load_explicit(&(fut)->val, memory_order_relaxed) <= 0)
#define futex_assert_is_not_locked(fut) ((void)0)

#endif

static inline errno_t futex_allocate_waitq(futex_t *futex)
{
	return __SYSCALL1(SYS_WAITQ_CREATE, (sysarg_t) &futex->whandle);
}

/** Down the futex with timeout, composably.
 *
 * This means that when the operation fails due to a timeout or being
 * interrupted, the next futex_up() is ignored, which allows certain kinds of
 * composition of synchronization primitives.
 *
 * In most other circumstances, regular futex_down_timeout() is a better choice.
 *
 * @param futex Futex.
 *
 * @return ENOENT if there is no such virtual address.
 * @return ETIMEOUT if timeout expires.
 * @return EOK on success.
 * @return Error code from <errno.h> otherwise.
 *
 */
static inline errno_t futex_down_composable(futex_t *futex,
    const struct timespec *expires)
{
	// TODO: Add tests for this.

	assert(futex->whandle != CAP_NIL);

	if (atomic_fetch_sub_explicit(&futex->val, 1, memory_order_acquire) > 0)
		return EOK;

	/* There wasn't any token. We must defer to the underlying semaphore. */

	usec_t timeout;

	if (!expires) {
		/* No timeout. */
		timeout = 0;
	} else {
		if (expires->tv_sec == 0) {
			/* We can't just return ETIMEOUT. That wouldn't be composable. */
			timeout = 1;
		} else {
			struct timespec tv;
			getuptime(&tv);
			timeout = ts_gteq(&tv, expires) ? 1 :
			    NSEC2USEC(ts_sub_diff(expires, &tv));
		}

		assert(timeout > 0);
	}

	return __SYSCALL3(SYS_WAITQ_SLEEP, (sysarg_t) futex->whandle,
	    (sysarg_t) timeout, (sysarg_t) SYNCH_FLAGS_FUTEX);
}

/** Up the futex.
 *
 * @param futex Futex.
 *
 * @return ENOENT if there is no such virtual address.
 * @return EOK on success.
 * @return Error code from <errno.h> otherwise.
 *
 */
static inline errno_t futex_up(futex_t *futex)
{
	if (atomic_fetch_add_explicit(&futex->val, 1, memory_order_release) < 0)
		return __SYSCALL1(SYS_WAITQ_WAKEUP, (sysarg_t) futex->whandle);

	return EOK;
}

static inline errno_t futex_down_timeout(futex_t *futex,
    const struct timespec *expires)
{
	/*
	 * This combination of a "composable" sleep followed by futex_up() on
	 * failure is necessary to prevent breakage due to certain race
	 * conditions.
	 */
	errno_t rc = futex_down_composable(futex, expires);
	if (rc != EOK)
		futex_up(futex);
	return rc;
}

/** Try to down the futex.
 *
 * @param futex Futex.
 *
 * @return true if the futex was acquired.
 * @return false if the futex was not acquired.
 *
 */
static inline bool futex_trydown(futex_t *futex)
{
	/*
	 * We can't just use CAS here.
	 * If we don't succeed with CAS, we can't return failure
	 * because that would lead to spurious failures where
	 * futex_down_timeout returns ETIMEOUT despite there being
	 * available tokens. That would break some algorithms.
	 * We also don't want to loop on CAS indefinitely, because
	 * that would make the semaphore not wait-free, even when all
	 * atomic operations and the underlying base semaphore are all
	 * wait-free.
	 * It's much less trouble (and code bloat) to just do regular
	 * down_timeout(), with an already expired deadline.
	 */
	struct timespec tv = { .tv_sec = 0, .tv_nsec = 0 };
	return futex_down_timeout(futex, &tv) == EOK;
}

/** Down the futex.
 *
 * @param futex Futex.
 *
 * @return ENOENT if there is no such virtual address.
 * @return EOK on success.
 * @return Error code from <errno.h> otherwise.
 *
 */
static inline errno_t futex_down(futex_t *futex)
{
	return futex_down_timeout(futex, NULL);
}

#endif

/** @}
 */