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
71 struct ck_spinlock_ticket {
72 CK_SPINLOCK_TICKET_TYPE value;
73 };
74 typedef struct ck_spinlock_ticket ck_spinlock_ticket_t;
75 #define CK_SPINLOCK_TICKET_INITIALIZER { .value = 0 }
76
77 CK_CC_INLINE static void
ck_spinlock_ticket_init(struct ck_spinlock_ticket * ticket)78 ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket)
79 {
80
81 ticket->value = 0;
82 ck_pr_barrier();
83 return;
84 }
85
86 CK_CC_INLINE static bool
ck_spinlock_ticket_locked(struct ck_spinlock_ticket * ticket)87 ck_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
99 CK_CC_INLINE static void
ck_spinlock_ticket_lock(struct ck_spinlock_ticket * ticket)100 ck_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
121 CK_CC_INLINE static void
ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket * ticket,unsigned int c)122 ck_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
148 CK_CC_INLINE static bool
ck_spinlock_ticket_trylock(struct ck_spinlock_ticket * ticket)149 ck_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
169 CK_CC_INLINE static void
ck_spinlock_ticket_unlock(struct ck_spinlock_ticket * ticket)170 ck_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 */
191 struct ck_spinlock_ticket {
192 unsigned int next;
193 unsigned int position;
194 };
195 typedef struct ck_spinlock_ticket ck_spinlock_ticket_t;
196
197 #define CK_SPINLOCK_TICKET_INITIALIZER {.next = 0, .position = 0}
198
199 CK_CC_INLINE static void
ck_spinlock_ticket_init(struct ck_spinlock_ticket * ticket)200 ck_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
210 CK_CC_INLINE static bool
ck_spinlock_ticket_locked(struct ck_spinlock_ticket * ticket)211 ck_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
221 CK_CC_INLINE static void
ck_spinlock_ticket_lock(struct ck_spinlock_ticket * ticket)222 ck_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
241 CK_CC_INLINE static void
ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket * ticket,unsigned int c)242 ck_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
270 CK_CC_INLINE static void
ck_spinlock_ticket_unlock(struct ck_spinlock_ticket * ticket)271 ck_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
288 CK_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
292 CK_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