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