1/* 2 * Copyright 2010-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_SPINLOCK_TICKET_H 28#define CK_SPINLOCK_TICKET_H 29 30#include <ck_backoff.h> 31#include <ck_cc.h> 32#include <ck_elide.h> 33#include <ck_md.h> 34#include <ck_pr.h> 35#include <ck_stdbool.h> 36 37#ifndef CK_F_SPINLOCK_TICKET 38#define CK_F_SPINLOCK_TICKET 39/* 40 * If 16-bit or 32-bit increment is supported, implement support for 41 * trylock functionality on availability of 32-bit or 64-bit fetch-and-add 42 * and compare-and-swap. This code path is only applied to x86*. 43 */ 44#if defined(CK_MD_TSO) && (defined(__x86__) || defined(__x86_64__)) 45#if defined(CK_F_PR_FAA_32) && defined(CK_F_PR_INC_16) && defined(CK_F_PR_CAS_32) 46#define CK_SPINLOCK_TICKET_TYPE uint32_t 47#define CK_SPINLOCK_TICKET_TYPE_BASE uint16_t 48#define CK_SPINLOCK_TICKET_INC(x) ck_pr_inc_16(x) 49#define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_32(x, y, z) 50#define CK_SPINLOCK_TICKET_FAA(x, y) ck_pr_faa_32(x, y) 51#define CK_SPINLOCK_TICKET_LOAD(x) ck_pr_load_32(x) 52#define CK_SPINLOCK_TICKET_INCREMENT (0x00010000UL) 53#define CK_SPINLOCK_TICKET_MASK (0xFFFFUL) 54#define CK_SPINLOCK_TICKET_SHIFT (16) 55#elif defined(CK_F_PR_FAA_64) && defined(CK_F_PR_INC_32) && defined(CK_F_PR_CAS_64) 56#define CK_SPINLOCK_TICKET_TYPE uint64_t 57#define CK_SPINLOCK_TICKET_TYPE_BASE uint32_t 58#define CK_SPINLOCK_TICKET_INC(x) ck_pr_inc_32(x) 59#define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_64(x, y, z) 60#define CK_SPINLOCK_TICKET_FAA(x, y) ck_pr_faa_64(x, y) 61#define CK_SPINLOCK_TICKET_LOAD(x) ck_pr_load_64(x) 62#define CK_SPINLOCK_TICKET_INCREMENT (0x0000000100000000ULL) 63#define CK_SPINLOCK_TICKET_MASK (0xFFFFFFFFULL) 64#define CK_SPINLOCK_TICKET_SHIFT (32) 65#endif 66#endif /* CK_MD_TSO */ 67 68#if defined(CK_SPINLOCK_TICKET_TYPE) 69#define CK_F_SPINLOCK_TICKET_TRYLOCK 70 71struct ck_spinlock_ticket { 72 CK_SPINLOCK_TICKET_TYPE value; 73}; 74typedef struct ck_spinlock_ticket ck_spinlock_ticket_t; 75#define CK_SPINLOCK_TICKET_INITIALIZER { .value = 0 } 76 77CK_CC_INLINE static void 78ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket) 79{ 80 81 ticket->value = 0; 82 ck_pr_barrier(); 83 return; 84} 85 86CK_CC_INLINE static bool 87ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket) 88{ 89 CK_SPINLOCK_TICKET_TYPE request, position; 90 91 request = CK_SPINLOCK_TICKET_LOAD(&ticket->value); 92 position = request & CK_SPINLOCK_TICKET_MASK; 93 request >>= CK_SPINLOCK_TICKET_SHIFT; 94 95 ck_pr_fence_acquire(); 96 return request != position; 97} 98 99CK_CC_INLINE static void 100ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket) 101{ 102 CK_SPINLOCK_TICKET_TYPE request, position; 103 104 /* Get our ticket number and set next ticket number. */ 105 request = CK_SPINLOCK_TICKET_FAA(&ticket->value, 106 CK_SPINLOCK_TICKET_INCREMENT); 107 108 position = request & CK_SPINLOCK_TICKET_MASK; 109 request >>= CK_SPINLOCK_TICKET_SHIFT; 110 111 while (request != position) { 112 ck_pr_stall(); 113 position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) & 114 CK_SPINLOCK_TICKET_MASK; 115 } 116 117 ck_pr_fence_lock(); 118 return; 119} 120 121CK_CC_INLINE static void 122ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c) 123{ 124 CK_SPINLOCK_TICKET_TYPE request, position; 125 ck_backoff_t backoff; 126 127 /* Get our ticket number and set next ticket number. */ 128 request = CK_SPINLOCK_TICKET_FAA(&ticket->value, 129 CK_SPINLOCK_TICKET_INCREMENT); 130 131 position = request & CK_SPINLOCK_TICKET_MASK; 132 request >>= CK_SPINLOCK_TICKET_SHIFT; 133 134 while (request != position) { 135 ck_pr_stall(); 136 position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) & 137 CK_SPINLOCK_TICKET_MASK; 138 139 backoff = (request - position) & CK_SPINLOCK_TICKET_MASK; 140 backoff <<= c; 141 ck_backoff_eb(&backoff); 142 } 143 144 ck_pr_fence_lock(); 145 return; 146} 147 148CK_CC_INLINE static bool 149ck_spinlock_ticket_trylock(struct ck_spinlock_ticket *ticket) 150{ 151 CK_SPINLOCK_TICKET_TYPE snapshot, request, position; 152 153 snapshot = CK_SPINLOCK_TICKET_LOAD(&ticket->value); 154 position = snapshot & CK_SPINLOCK_TICKET_MASK; 155 request = snapshot >> CK_SPINLOCK_TICKET_SHIFT; 156 157 if (position != request) 158 return false; 159 160 if (CK_SPINLOCK_TICKET_CAS(&ticket->value, 161 snapshot, snapshot + CK_SPINLOCK_TICKET_INCREMENT) == false) { 162 return false; 163 } 164 165 ck_pr_fence_lock(); 166 return true; 167} 168 169CK_CC_INLINE static void 170ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket) 171{ 172 173 ck_pr_fence_unlock(); 174 CK_SPINLOCK_TICKET_INC((CK_SPINLOCK_TICKET_TYPE_BASE *)(void *)&ticket->value); 175 return; 176} 177 178#undef CK_SPINLOCK_TICKET_TYPE 179#undef CK_SPINLOCK_TICKET_TYPE_BASE 180#undef CK_SPINLOCK_TICKET_INC 181#undef CK_SPINLOCK_TICKET_FAA 182#undef CK_SPINLOCK_TICKET_LOAD 183#undef CK_SPINLOCK_TICKET_INCREMENT 184#undef CK_SPINLOCK_TICKET_MASK 185#undef CK_SPINLOCK_TICKET_SHIFT 186#else 187/* 188 * MESI benefits from cacheline padding between next and current. This avoids 189 * invalidation of current from the cache due to incoming lock requests. 190 */ 191struct ck_spinlock_ticket { 192 unsigned int next; 193 unsigned int position; 194}; 195typedef struct ck_spinlock_ticket ck_spinlock_ticket_t; 196 197#define CK_SPINLOCK_TICKET_INITIALIZER {.next = 0, .position = 0} 198 199CK_CC_INLINE static void 200ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket) 201{ 202 203 ticket->next = 0; 204 ticket->position = 0; 205 ck_pr_barrier(); 206 207 return; 208} 209 210CK_CC_INLINE static bool 211ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket) 212{ 213 bool r; 214 215 r = ck_pr_load_uint(&ticket->position) != 216 ck_pr_load_uint(&ticket->next); 217 ck_pr_fence_acquire(); 218 return r; 219} 220 221CK_CC_INLINE static void 222ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket) 223{ 224 unsigned int request; 225 226 /* Get our ticket number and set next ticket number. */ 227 request = ck_pr_faa_uint(&ticket->next, 1); 228 229 /* 230 * Busy-wait until our ticket number is current. 231 * We can get away without a fence here assuming 232 * our position counter does not overflow. 233 */ 234 while (ck_pr_load_uint(&ticket->position) != request) 235 ck_pr_stall(); 236 237 ck_pr_fence_lock(); 238 return; 239} 240 241CK_CC_INLINE static void 242ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c) 243{ 244 ck_backoff_t backoff; 245 unsigned int request, position; 246 247 request = ck_pr_faa_uint(&ticket->next, 1); 248 249 for (;;) { 250 position = ck_pr_load_uint(&ticket->position); 251 if (position == request) 252 break; 253 254 backoff = request - position; 255 backoff <<= c; 256 257 /* 258 * Ideally, back-off from generating cache traffic for at least 259 * the amount of time necessary for the number of pending lock 260 * acquisition and relinquish operations (assuming an empty 261 * critical section). 262 */ 263 ck_backoff_eb(&backoff); 264 } 265 266 ck_pr_fence_lock(); 267 return; 268} 269 270CK_CC_INLINE static void 271ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket) 272{ 273 unsigned int update; 274 275 ck_pr_fence_unlock(); 276 277 /* 278 * Update current ticket value so next lock request can proceed. 279 * Overflow behavior is assumed to be roll-over, in which case, 280 * it is only an issue if there are 2^32 pending lock requests. 281 */ 282 update = ck_pr_load_uint(&ticket->position); 283 ck_pr_store_uint(&ticket->position, update + 1); 284 return; 285} 286#endif /* !CK_F_SPINLOCK_TICKET_TRYLOCK */ 287 288CK_ELIDE_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t, 289 ck_spinlock_ticket_locked, ck_spinlock_ticket_lock, 290 ck_spinlock_ticket_locked, ck_spinlock_ticket_unlock) 291 292CK_ELIDE_TRYLOCK_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t, 293 ck_spinlock_ticket_locked, ck_spinlock_ticket_trylock) 294 295#endif /* CK_F_SPINLOCK_TICKET */ 296#endif /* CK_SPINLOCK_TICKET_H */ 297