10Sduke/*
22362Sohair * Copyright 2013-2015 Samy Al Bahra.
30Sduke * All rights reserved.
40Sduke *
50Sduke * Redistribution and use in source and binary forms, with or without
60Sduke * modification, are permitted provided that the following conditions
70Sduke * are met:
80Sduke * 1. Redistributions of source code must retain the above copyright
90Sduke *    notice, this list of conditions and the following disclaimer.
100Sduke * 2. Redistributions in binary form must reproduce the above copyright
110Sduke *    notice, this list of conditions and the following disclaimer in the
120Sduke *    documentation and/or other materials provided with the distribution.
130Sduke *
140Sduke * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
150Sduke * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
160Sduke * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
170Sduke * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
180Sduke * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
192362Sohair * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
202362Sohair * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
212362Sohair * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
220Sduke * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
230Sduke * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
240Sduke * SUCH DAMAGE.
250Sduke */
260Sduke
270Sduke#ifndef CK_ELIDE_H
280Sduke#define CK_ELIDE_H
290Sduke
300Sduke/*
310Sduke * As RTM is currently only supported on TSO x86 architectures,
320Sduke * fences have been omitted. They will be necessary for other
330Sduke * non-TSO architectures with TM support.
340Sduke */
350Sduke
360Sduke#include <ck_cc.h>
370Sduke#include <ck_pr.h>
380Sduke#include <ck_string.h>
390Sduke
400Sduke/*
410Sduke * skip_-prefixed counters represent the number of consecutive
420Sduke * elisions to forfeit. retry_-prefixed counters represent the
430Sduke * number of elision retries to attempt before forfeit.
440Sduke *
450Sduke *     _busy: Lock was busy
460Sduke *    _other: Unknown explicit abort
47 * _conflict: Data conflict in elision section
48 */
49struct ck_elide_config {
50	unsigned short skip_busy;
51	short retry_busy;
52	unsigned short skip_other;
53	short retry_other;
54	unsigned short skip_conflict;
55	short retry_conflict;
56};
57
58#define CK_ELIDE_CONFIG_DEFAULT_INITIALIZER {	\
59	.skip_busy = 5,				\
60	.retry_busy = 256,			\
61	.skip_other = 3,			\
62	.retry_other = 3,			\
63	.skip_conflict = 2,			\
64	.retry_conflict = 5			\
65}
66
67struct ck_elide_stat {
68	unsigned int n_fallback;
69	unsigned int n_elide;
70	unsigned short skip;
71};
72typedef struct ck_elide_stat ck_elide_stat_t;
73
74#define CK_ELIDE_STAT_INITIALIZER { 0, 0, 0 }
75
76CK_CC_INLINE static void
77ck_elide_stat_init(ck_elide_stat_t *st)
78{
79
80	memset(st, 0, sizeof(*st));
81	return;
82}
83
84#ifdef CK_F_PR_RTM
85enum _ck_elide_hint {
86	CK_ELIDE_HINT_RETRY = 0,
87	CK_ELIDE_HINT_SPIN,
88	CK_ELIDE_HINT_STOP
89};
90
91#define CK_ELIDE_LOCK_BUSY 0xFF
92
93static enum _ck_elide_hint
94_ck_elide_fallback(int *retry,
95    struct ck_elide_stat *st,
96    struct ck_elide_config *c,
97    unsigned int status)
98{
99
100	st->n_fallback++;
101	if (*retry > 0)
102		return CK_ELIDE_HINT_RETRY;
103
104	if (st->skip != 0)
105		return CK_ELIDE_HINT_STOP;
106
107	if (status & CK_PR_RTM_EXPLICIT) {
108		if (CK_PR_RTM_CODE(status) == CK_ELIDE_LOCK_BUSY) {
109			st->skip = c->skip_busy;
110			*retry = c->retry_busy;
111			return CK_ELIDE_HINT_SPIN;
112		}
113
114		st->skip = c->skip_other;
115		return CK_ELIDE_HINT_STOP;
116	}
117
118	if ((status & CK_PR_RTM_RETRY) &&
119	    (status & CK_PR_RTM_CONFLICT)) {
120		st->skip = c->skip_conflict;
121		*retry = c->retry_conflict;
122		return CK_ELIDE_HINT_RETRY;
123	}
124
125	/*
126	 * Capacity, debug and nesting abortions are likely to be
127	 * invariant conditions for the acquisition, execute regular
128	 * path instead. If retry bit is not set, then take the hint.
129	 */
130	st->skip = USHRT_MAX;
131	return CK_ELIDE_HINT_STOP;
132}
133
134/*
135 * Defines an elision implementation according to the following variables:
136 *     N - Namespace of elision implementation.
137 *     T - Typename of mutex.
138 *   L_P - Lock predicate, returns false if resource is available.
139 *     L - Function to call if resource is unavailable of transaction aborts.
140 *   U_P - Unlock predicate, returns false if elision failed.
141 *     U - Function to call if transaction failed.
142 */
143#define CK_ELIDE_PROTOTYPE(N, T, L_P, L, U_P, U)					\
144	CK_CC_INLINE static void							\
145	ck_elide_##N##_lock_adaptive(T *lock,						\
146	    struct ck_elide_stat *st,							\
147	    struct ck_elide_config *c)							\
148	{										\
149		enum _ck_elide_hint hint;						\
150		int retry;								\
151											\
152		if (CK_CC_UNLIKELY(st->skip != 0)) {					\
153			st->skip--;							\
154			goto acquire;							\
155		}									\
156											\
157		retry = c->retry_conflict;						\
158		do {									\
159			unsigned int status = ck_pr_rtm_begin();			\
160			if (status == CK_PR_RTM_STARTED) {				\
161				if (L_P(lock) == true)					\
162					ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);		\
163											\
164				return;							\
165			}								\
166											\
167			hint = _ck_elide_fallback(&retry, st, c, status);		\
168			if (hint == CK_ELIDE_HINT_RETRY)				\
169				continue;						\
170											\
171			if (hint == CK_ELIDE_HINT_SPIN) {				\
172				while (--retry != 0) {					\
173					if (L_P(lock) == false)				\
174						break;					\
175											\
176					ck_pr_stall();					\
177				}							\
178											\
179				continue;						\
180			}								\
181											\
182			if (hint == CK_ELIDE_HINT_STOP)					\
183				break;							\
184		} while (CK_CC_LIKELY(--retry > 0));					\
185											\
186	acquire:									\
187		L(lock);								\
188		return;									\
189	}										\
190	CK_CC_INLINE static void							\
191	ck_elide_##N##_unlock_adaptive(struct ck_elide_stat *st, T *lock)		\
192	{										\
193											\
194		if (U_P(lock) == false) {						\
195			ck_pr_rtm_end();						\
196			st->skip = 0;							\
197			st->n_elide++;							\
198		} else {								\
199			U(lock);							\
200		}									\
201											\
202		return;									\
203	}										\
204	CK_CC_INLINE static void							\
205	ck_elide_##N##_lock(T *lock)							\
206	{										\
207											\
208		if (ck_pr_rtm_begin() != CK_PR_RTM_STARTED) {				\
209			L(lock);							\
210			return;								\
211		}									\
212											\
213		if (L_P(lock) == true)							\
214			ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);				\
215											\
216		return;									\
217	}										\
218	CK_CC_INLINE static void							\
219	ck_elide_##N##_unlock(T *lock)							\
220	{										\
221											\
222		if (U_P(lock) == false) {						\
223			ck_pr_rtm_end();						\
224		} else {								\
225			U(lock);							\
226		}									\
227											\
228		return;									\
229	}
230
231#define CK_ELIDE_TRYLOCK_PROTOTYPE(N, T, TL_P, TL)			\
232	CK_CC_INLINE static bool					\
233	ck_elide_##N##_trylock(T *lock)					\
234	{								\
235									\
236		if (ck_pr_rtm_begin() != CK_PR_RTM_STARTED)		\
237			return false;					\
238									\
239		if (TL_P(lock) == true)					\
240			ck_pr_rtm_abort(CK_ELIDE_LOCK_BUSY);		\
241									\
242		return true;						\
243	}
244#else
245/*
246 * If RTM is not enabled on the target platform (CK_F_PR_RTM) then these
247 * elision wrappers directly calls into the user-specified lock operations.
248 * Unfortunately, the storage cost of both ck_elide_config and ck_elide_stat
249 * are paid (typically a storage cost that is a function of lock objects and
250 * thread count).
251 */
252#define CK_ELIDE_PROTOTYPE(N, T, L_P, L, U_P, U)			\
253	CK_CC_INLINE static void					\
254	ck_elide_##N##_lock_adaptive(T *lock,				\
255	    struct ck_elide_stat *st,					\
256	    struct ck_elide_config *c)					\
257	{								\
258									\
259		(void)st;						\
260		(void)c;						\
261		L(lock);						\
262		return;							\
263	}								\
264	CK_CC_INLINE static void					\
265	ck_elide_##N##_unlock_adaptive(struct ck_elide_stat *st,	\
266	    T *lock)							\
267	{								\
268									\
269		(void)st;						\
270		U(lock);						\
271		return;							\
272	}								\
273	CK_CC_INLINE static void					\
274	ck_elide_##N##_lock(T *lock)					\
275	{								\
276									\
277		L(lock);						\
278		return;							\
279	}								\
280	CK_CC_INLINE static void					\
281	ck_elide_##N##_unlock(T *lock)					\
282	{								\
283									\
284		U(lock);						\
285		return;							\
286	}
287
288#define CK_ELIDE_TRYLOCK_PROTOTYPE(N, T, TL_P, TL)			\
289	CK_CC_INLINE static bool					\
290	ck_elide_##N##_trylock(T *lock)					\
291	{								\
292									\
293		return TL_P(lock);					\
294	}
295#endif /* !CK_F_PR_RTM */
296
297/*
298 * Best-effort elision lock operations. First argument is name (N)
299 * associated with implementation and the second is a pointer to
300 * the type specified above (T).
301 *
302 * Unlike the adaptive variant, this interface does not have any retry
303 * semantics. In environments where jitter is low, this may yield a tighter
304 * fast path.
305 */
306#define CK_ELIDE_LOCK(NAME, LOCK)	ck_elide_##NAME##_lock(LOCK)
307#define CK_ELIDE_UNLOCK(NAME, LOCK)	ck_elide_##NAME##_unlock(LOCK)
308#define CK_ELIDE_TRYLOCK(NAME, LOCK)	ck_elide_##NAME##_trylock(LOCK)
309
310/*
311 * Adaptive elision lock operations. In addition to name and pointer
312 * to the lock, you must pass in a pointer to an initialized
313 * ck_elide_config structure along with a per-thread stat structure.
314 */
315#define CK_ELIDE_LOCK_ADAPTIVE(NAME, STAT, CONFIG, LOCK) \
316	ck_elide_##NAME##_lock_adaptive(LOCK, STAT, CONFIG)
317
318#define CK_ELIDE_UNLOCK_ADAPTIVE(NAME, STAT, LOCK) \
319	ck_elide_##NAME##_unlock_adaptive(STAT, LOCK)
320
321#endif /* CK_ELIDE_H */
322