summaryrefslogtreecommitdiffstats
path: root/include/ck_elide.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2021-07-23 11:24:09 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2021-07-23 11:24:09 +0000
commite36b37583bebd229102f46c4ed7d2f6fad8697d4 (patch)
tree73937b6f051fcaaa1ccbdfbaa9f3a1f36bbedb9e /include/ck_elide.h
parentInitial commit. (diff)
downloadck-e36b37583bebd229102f46c4ed7d2f6fad8697d4.tar.xz
ck-e36b37583bebd229102f46c4ed7d2f6fad8697d4.zip
Adding upstream version 0.6.0.upstream/0.6.0
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'include/ck_elide.h')
-rw-r--r--include/ck_elide.h321
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 */