Adding upstream version 0.6.0.upstream/0.6.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 321 insertions, 0 deletions

diff --git a/include/ck_elide.h b/include/ck_elide.h
new file mode 100644
index 0000000..1b90041
--- /dev/null
+++ b/include/ck_elide.h
@@ -0,0 +1,321 @@
+/*
+ * 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 */