diff options
Diffstat (limited to 'include/ck_elide.h')
| -rw-r--r-- | include/ck_elide.h | 321 |
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 */ |