ck_elide.h

/*
 * Copyright 2013-2015 Samy Al Bahra.
 * 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.
 */

#ifndef CK_ELIDE_H
#define CK_ELIDE_H

/*
 * As RTM is currently only supported on TSO x86 architectures,
 * fences have been omitted. They will be necessary for other
 * non-TSO architectures with TM support.
 */

#include <ck_cc.h>
#include <ck_pr.h>
#include <ck_string.h>

/*
 * skip_-prefixed counters represent the number of consecutive
 * elisions to forfeit. retry_-prefixed counters represent the
 * number of elision retries to attempt before forfeit.
 *
 *     _busy: Lock was busy
 *    _other: Unknown explicit abort
 * _conflict: Data conflict in elision section
 */
struct ck_elide_config {
	unsigned short skip_busy;
	short retry_busy;
	unsigned short skip_other;
	short retry_other;
	unsigned short skip_conflict;
	short retry_conflict;
};

#define CK_ELIDE_CONFIG_DEFAULT_INITIALIZER {	\
	.skip_busy = 5,				\
	.retry_busy = 256,			\
	.skip_other = 3,			\
	.retry_other = 3,			\
	.skip_conflict = 2,			\
	.retry_conflict = 5			\
}

struct ck_elide_stat {
	unsigned int n_fallback;
	unsigned int n_elide;
	unsigned short skip;
};
typedef struct ck_elide_stat ck_elide_stat_t;

#define CK_ELIDE_STAT_INITIALIZER { 0, 0, 0 }

CK_CC_INLINE static void
ck_elide_stat_init(ck_elide_stat_t *st)
{

	memset(st, 0, sizeof(*st));
	return;
}

#ifdef CK_F_PR_RTM
enum _ck_elide_hint {
	CK_ELIDE_HINT_RETRY = 0,
	CK_ELIDE_HINT_SPIN,
	CK_ELIDE_HINT_STOP
};

#define CK_ELIDE_LOCK_BUSY 0xFF

static enum _ck_elide_hint
_ck_elide_fallback(int *retry,
    struct ck_elide_stat *st,
    struct ck_elide_config *c,
    unsigned int status)
{

	st->n_fallback++;
	if (*retry > 0)
		return CK_ELIDE_HINT_RETRY;

	if (st->skip != 0)
		return CK_ELIDE_HINT_STOP;

	if (status & CK_PR_RTM_EXPLICIT) {
		if (CK_PR_RTM_CODE(status) == CK_ELIDE_LOCK_BUSY) {
			st->skip = c->skip_busy;
			*retry = c->retry_busy;
			return CK_ELIDE_HINT_SPIN;
		}

		st->skip = c->skip_other;
		return CK_ELIDE_HINT_STOP;
	}

	if ((status & CK_PR_RTM_RETRY) &&
	    (status & CK_PR_RTM_CONFLICT)) {
		st->skip = c->skip_conflict;
		*retry = c->retry_conflict;
		return CK_ELIDE_HINT_RETRY;
	}

	/*
	 * Capacity, debug and nesting abortions are likely to be
	 * invariant conditions for the acquisition, execute regular
	 * path instead. If retry bit is not set, then take the hint.
	 */
	st->skip = USHRT_MAX;
	return CK_ELIDE_HINT_STOP;
}

/*
 * Defines an elision implementation according to the following variables:
 *     N - Namespace of elision implementation.
 *     T - Typename of mutex.
 *   L_P - Lock predicate, returns false if resource is available.
 *     L - Function to call if resource is unavailable of transaction aborts.
 *   U_P - Unlock predicate, returns false if elision failed.
 *     U - Function to call if transaction failed.
 */
#define CK_ELIDE_PROTOTYPE(N, T, L_P, L, U_P, U)					\
	CK_CC_INLINE static void							\
	ck_elide_##N##_lock_adaptive(T *lock,						\
	    struct ck_elide_stat *st,							\
	    struct ck_elide_config *c)							\
	{										\
		enum _ck_elide_hint hint;						\
		int retry;								\
											\
		if (CK_CC_UNLIKELY(st->skip != 0)) {					\
			st->skip--;							\
			goto acquire;							\
		}									\
											\
		retry = c->retry_conflict;						\
		do {									\
			unsigned int status = ck_pr_rtm_begin();			\
			if (status == CK_PR_RTM_STARTED) {				\
				if (L_P(lock) == true)					\
					ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);		\
											\
				return;							\
			}								\
											\
			hint = _ck_elide_fallback(&retry, st, c, status);		\
			if (hint == CK_ELIDE_HINT_RETRY)				\
				continue;						\
											\
			if (hint == CK_ELIDE_HINT_SPIN) {				\
				while (--retry != 0) {					\
					if (L_P(lock) == false)				\
						break;					\
											\
					ck_pr_stall();					\
				}							\
											\
				continue;						\
			}								\
											\
			if (hint == CK_ELIDE_HINT_STOP)					\
				break;							\
		} while (CK_CC_LIKELY(--retry > 0));					\
											\
	acquire:									\
		L(lock);								\
		return;									\
	}										\
	CK_CC_INLINE static void							\
	ck_elide_##N##_unlock_adaptive(struct ck_elide_stat *st, T *lock)		\
	{										\
											\
		if (U_P(lock) == false) {						\
			ck_pr_rtm_end();						\
			st->skip = 0;							\
			st->n_elide++;							\
		} else {								\
			U(lock);							\
		}									\
											\
		return;									\
	}										\
	CK_CC_INLINE static void							\
	ck_elide_##N##_lock(T *lock)							\
	{										\
											\
		if (ck_pr_rtm_begin() != CK_PR_RTM_STARTED) {				\
			L(lock);							\
			return;								\
		}									\
											\
		if (L_P(lock) == true)							\
			ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);				\
											\
		return;									\
	}										\
	CK_CC_INLINE static void							\
	ck_elide_##N##_unlock(T *lock)							\
	{										\
											\
		if (U_P(lock) == false) {						\
			ck_pr_rtm_end();						\
		} else {								\
			U(lock);							\
		}									\
											\
		return;									\
	}

#define CK_ELIDE_TRYLOCK_PROTOTYPE(N, T, TL_P, TL)			\
	CK_CC_INLINE static bool					\
	ck_elide_##N##_trylock(T *lock)					\
	{								\
									\
		if (ck_pr_rtm_begin() != CK_PR_RTM_STARTED)		\
			return false;					\
									\
		if (TL_P(lock) == true)					\
			ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);		\
									\
		return true;						\
	}
#else
/*
 * If RTM is not enabled on the target platform (CK_F_PR_RTM) then these
 * elision wrappers directly calls into the user-specified lock operations.
 * Unfortunately, the storage cost of both ck_elide_config and ck_elide_stat
 * are paid (typically a storage cost that is a function of lock objects and
 * thread count).
 */
#define CK_ELIDE_PROTOTYPE(N, T, L_P, L, U_P, U)			\
	CK_CC_INLINE static void					\
	ck_elide_##N##_lock_adaptive(T *lock,				\
	    struct ck_elide_stat *st,					\
	    struct ck_elide_config *c)					\
	{								\
									\
		(void)st;						\
		(void)c;						\
		L(lock);						\
		return;							\
	}								\
	CK_CC_INLINE static void					\
	ck_elide_##N##_unlock_adaptive(struct ck_elide_stat *st,	\
	    T *lock)							\
	{								\
									\
		(void)st;						\
		U(lock);						\
		return;							\
	}								\
	CK_CC_INLINE static void					\
	ck_elide_##N##_lock(T *lock)					\
	{								\
									\
		L(lock);						\
		return;							\
	}								\
	CK_CC_INLINE static void					\
	ck_elide_##N##_unlock(T *lock)					\
	{								\
									\
		U(lock);						\
		return;							\
	}

#define CK_ELIDE_TRYLOCK_PROTOTYPE(N, T, TL_P, TL)			\
	CK_CC_INLINE static bool					\
	ck_elide_##N##_trylock(T *lock)					\
	{								\
									\
		return TL_P(lock);					\
	}
#endif /* !CK_F_PR_RTM */

/*
 * Best-effort elision lock operations. First argument is name (N)
 * associated with implementation and the second is a pointer to
 * the type specified above (T).
 *
 * Unlike the adaptive variant, this interface does not have any retry
 * semantics. In environments where jitter is low, this may yield a tighter
 * fast path.
 */
#define CK_ELIDE_LOCK(NAME, LOCK)	ck_elide_##NAME##_lock(LOCK)
#define CK_ELIDE_UNLOCK(NAME, LOCK)	ck_elide_##NAME##_unlock(LOCK)
#define CK_ELIDE_TRYLOCK(NAME, LOCK)	ck_elide_##NAME##_trylock(LOCK)

/*
 * Adaptive elision lock operations. In addition to name and pointer
 * to the lock, you must pass in a pointer to an initialized
 * ck_elide_config structure along with a per-thread stat structure.
 */
#define CK_ELIDE_LOCK_ADAPTIVE(NAME, STAT, CONFIG, LOCK) \
	ck_elide_##NAME##_lock_adaptive(LOCK, STAT, CONFIG)

#define CK_ELIDE_UNLOCK_ADAPTIVE(NAME, STAT, LOCK) \
	ck_elide_##NAME##_unlock_adaptive(STAT, LOCK)

#endif /* CK_ELIDE_H */