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