1 /* 2 * Copyright 2013-2015 Samy Al Bahra. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 #ifndef CK_ELIDE_H 28 #define CK_ELIDE_H 29 30 /* 31 * As RTM is currently only supported on TSO x86 architectures, 32 * fences have been omitted. They will be necessary for other 33 * non-TSO architectures with TM support. 34 */ 35 36 #include <ck_cc.h> 37 #include <ck_pr.h> 38 #include <ck_string.h> 39 40 /* 41 * skip_-prefixed counters represent the number of consecutive 42 * elisions to forfeit. retry_-prefixed counters represent the 43 * number of elision retries to attempt before forfeit. 44 * 45 * _busy: Lock was busy 46 * _other: Unknown explicit abort 47 * _conflict: Data conflict in elision section 48 */ 49 struct 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 67 struct ck_elide_stat { 68 unsigned int n_fallback; 69 unsigned int n_elide; 70 unsigned short skip; 71 }; 72 typedef struct ck_elide_stat ck_elide_stat_t; 73 74 #define CK_ELIDE_STAT_INITIALIZER { 0, 0, 0 } 75 76 CK_CC_INLINE static void 77 ck_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 85 enum _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 93 static 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