PerformanceTests/StitchMarker/ck/include/ck_elide.h - WebKit - Git at Google

 /*
  * 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 */
	/*
	* 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 */