1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
.\"
.\" Copyright 2013 Samy Al Bahra.
.\" All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\" notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\" notice, this list of conditions and the following disclaimer in the
.\" documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"
.Dd July 26, 2013.
.Dt ck_spinlock 3
.Sh NAME
.Nm ck_spinlock_init ,
.Nm ck_spinlock_lock ,
.Nm ck_spinlock_unlock ,
.Nm ck_spinlock_locked ,
.Nm ck_spinlock_trylock ,
.Nm ck_spinlock_anderson_init ,
.Nm ck_spinlock_anderson_locked ,
.Nm ck_spinlock_anderson_lock ,
.Nm ck_spinlock_anderson_unlock ,
.Nm ck_spinlock_cas_init ,
.Nm ck_spinlock_cas_locked ,
.Nm ck_spinlock_cas_lock ,
.Nm ck_spinlock_cas_lock_eb ,
.Nm ck_spinlock_cas_trylock ,
.Nm ck_spinlock_cas_unlock ,
.Nm ck_spinlock_clh_init ,
.Nm ck_spinlock_clh_locked ,
.Nm ck_spinlock_clh_lock ,
.Nm ck_spinlock_clh_unlock ,
.Nm ck_spinlock_dec_init ,
.Nm ck_spinlock_dec_locked ,
.Nm ck_spinlock_dec_lock ,
.Nm ck_spinlock_dec_lock_eb ,
.Nm ck_spinlock_dec_trylock ,
.Nm ck_spinlock_dec_unlock ,
.Nm ck_spinlock_fas_init ,
.Nm ck_spinlock_fas_lock ,
.Nm ck_spinlock_fas_lock_eb ,
.Nm ck_spinlock_fas_locked ,
.Nm ck_spinlock_fas_trylock ,
.Nm ck_spinlock_fas_unlock ,
.Nm ck_spinlock_hclh_init ,
.Nm ck_spinlock_hclh_locked ,
.Nm ck_spinlock_hclh_lock ,
.Nm ck_spinlock_hclh_unlock ,
.Nm ck_spinlock_mcs_init ,
.Nm ck_spinlock_mcs_locked ,
.Nm ck_spinlock_mcs_lock ,
.Nm ck_spinlock_mcs_trylock ,
.Nm ck_spinlock_mcs_unlock ,
.Nm ck_spinlock_ticket_init ,
.Nm ck_spinlock_ticket_locked ,
.Nm ck_spinlock_ticket_lock ,
.Nm ck_spinlock_ticket_lock_pb ,
.Nm ck_spinlock_ticket_trylock ,
.Nm ck_spinlock_ticket_unlock
.Nd spinlock implementations
.Sh LIBRARY
Concurrency Kit (libck, \-lck)
.Sh SYNOPSIS
.In ck_spinlock.h
.Pp
.Dv ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;
.Ft void
.Fn ck_spinlock_init "ck_spinlock_t *lock"
.Ft void
.Fn ck_spinlock_lock "ck_spinlock_t *lock"
.Ft void
.Fn ck_spinlock_unlock "ck_spinlock_t *lock"
.Ft bool
.Fn ck_spinlock_locked "ck_spinlock_t *lock"
.Ft bool
.Fn ck_spinlock_trylock "ck_spinlock_t *lock"
.Ft void
.Fn ck_spinlock_anderson_init "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slots" "unsigned int count"
.Ft bool
.Fn ck_spinlock_anderson_locked "ck_spinlock_anderson_t *lock"
.Ft void
.Fn ck_spinlock_anderson_lock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t **slot"
.Ft void
.Fn ck_spinlock_anderson_unlock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slot"
.Pp
.Dv ck_spinlock_cas_t spinlock = CK_SPINLOCK_CAS_INITIALIZER;
.Ft void
.Fn ck_spinlock_cas_init "ck_spinlock_cas_t *lock"
.Ft bool
.Fn ck_spinlock_cas_locked "ck_spinlock_cas_t *lock"
.Ft void
.Fn ck_spinlock_cas_lock "ck_spinlock_cas_t *lock"
.Ft void
.Fn ck_spinlock_cas_lock_eb "ck_spinlock_cas_t *lock"
.Ft bool
.Fn ck_spinlock_cas_trylock "ck_spinlock_cas_t *lock"
.Ft void
.Fn ck_spinlock_cas_unlock "ck_spinlock_cas_t *lock"
.Ft void
.Fn ck_spinlock_clh_init "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *unowned"
.Ft bool
.Fn ck_spinlock_clh_locked "ck_spinlock_clh_t **lock"
.Ft void
.Fn ck_spinlock_clh_lock "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *node"
.Ft void
.Fn ck_spinlock_clh_unlock "ck_spinlock_clh_t **node"
.Pp
.Dv ck_spinlock_dec_t spinlock = CK_SPINLOCK_DEC_INITIALIZER;
.Ft void
.Fn ck_spinlock_dec_init "ck_spinlock_dec_t *lock"
.Ft bool
.Fn ck_spinlock_dec_locked "ck_spinlock_dec_t *lock"
.Ft void
.Fn ck_spinlock_dec_lock "ck_spinlock_dec_t *lock"
.Ft void
.Fn ck_spinlock_dec_lock_eb "ck_spinlock_dec_t *lock"
.Ft bool
.Fn ck_spinlock_dec_trylock "ck_spinlock_dec_t *lock"
.Ft void
.Fn ck_spinlock_dec_unlock "ck_spinlock_dec_t *lock"
.Pp
.Dv ck_spinlock_fas_t spinlock = CK_SPINLOCK_FAS_INITIALIZER;
.Ft void
.Fn ck_spinlock_fas_init "ck_spinlock_fas_t *lock"
.Ft void
.Fn ck_spinlock_fas_lock "ck_spinlock_fas_t *lock"
.Ft void
.Fn ck_spinlock_fas_lock_eb "ck_spinlock_fas_t *lock"
.Ft bool
.Fn ck_spinlock_fas_locked "ck_spinlock_fas_t *lock"
.Ft bool
.Fn ck_spinlock_fas_trylock "ck_spinlock_fas_t *lock"
.Ft void
.Fn ck_spinlock_fas_unlock "ck_spinlock_fas_t *lock"
.Pp
.Ft void
.Fn ck_spinlock_hclh_init "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *unowned"
.Ft bool
.Fn ck_spinlock_hclh_locked "ck_spinlock_hclh_t **lock"
.Ft void
.Fn ck_spinlock_hclh_lock "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *node"
.Ft void
.Fn ck_spinlock_hclh_unlock "ck_spinlock_hclh_t **node"
.Pp
.Dv ck_spinlock_mcs_t spinlock = CK_SPINLOCK_MCS_INITIALIZER;
.Ft void
.Fn ck_spinlock_mcs_init "ck_spinlock_mcs_t **lock"
.Ft bool
.Fn ck_spinlock_mcs_locked "ck_spinlock_mcs_t **lock"
.Ft void
.Fn ck_spinlock_mcs_lock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
.Ft bool
.Fn ck_spinlock_mcs_trylock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
.Ft void
.Fn ck_spinlock_mcs_unlock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
.Pp
.Dv ck_spinlock_ticket_t spinlock = CK_SPINLOCK_TICKET_INITIALIZER;
.Ft void
.Fn ck_spinlock_ticket_init "ck_spinlock_ticket_t *lock"
.Ft bool
.Fn ck_spinlock_ticket_locked "ck_spinlock_ticket_t *lock"
.Ft void
.Fn ck_spinlock_ticket_lock "ck_spinlock_ticket_t *lock"
.Ft void
.Fn ck_spinlock_ticket_lock_pb "ck_spinlock_ticket_t *lock" "unsigned int period"
.Ft bool
.Fn ck_spinlock_ticket_trylock "ck_spinlock_ticket_t *lock"
.Ft void
.Fn ck_spinlock_ticket_unlock "ck_spinlock_ticket_t *lock"
.Sh DESCRIPTION
A family of busy-wait spinlock implementations. The ck_spinlock_t implementation is simply
a wrapper around the fetch-and-swap (ck_spinlock_fas_t) implementation. The table below
provides a summary of the current implementations.
.Bd -literal
| Namespace | Algorithm | Type | Restrictions | Fair |
\'----------------------|-----------------------------|---------------|-------------------------|--------'
ck_spinlock_anderson Anderson Array Fixed number of threads Yes
ck_spinlock_cas Compare-and-Swap Centralized None No
ck_spinlock_clh Craig, Landin and Hagersten Queue Lifetime requirements Yes
ck_spinlock_dec Decrement (Linux kernel) Centralized UINT_MAX concurrency No
ck_spinlock_fas Fetch-and-store Centralized None No
ck_spinlock_hclh Hierarchical CLH Queue Lifetime requirements Yes *
ck_spinlock_mcs Mellor-Crummey and Scott Queue None Yes
ck_spinlock_ticket Ticket Centralized None Yes
.Ed
.Pp
* Hierarchical CLH only offers weak fairness for threads accross cluster
nodes.
.Pp
If contention is low and there is no hard requirement for starvation-freedom
then a centralized greedy (unfair) spinlock is recommended. If contention is
high and there is no requirement for starvation-freedom then a centralized
greedy spinlock is recommended to be used with an exponential backoff
mechanism. If contention is generally low and there is a hard requirement for
starvation-freedom then the ticket lock is recommended. If contention is high
and there is a hard requirement for starvation-freedom then the Craig and
Landin and Hagersten queue spinlock is recommended unless stack allocation is
necessary or NUMA factor is high, in which case the Mellor-Crummey and Scott
spinlock is recommended. If you cannot afford O(n) space-usage from array
or queue spinlocks but still require fairness under high contention then
the ticket lock with proportional back-off is recommended.
If NUMA factor is high but prefer a greedy lock, then please see
.Xr ck_cohort 3 .
.Sh EXAMPLE
.Bd -literal -offset indent
#include <ck_spinlock.h>
#include <stdbool.h>
/*
* Alternatively, the mutex may be initialized at run-time with
* ck_spinlock_init(&mutex).
*/
ck_spinlock_t mutex = CK_SPINLOCK_INITIALIZER;
void
example(void)
{
ck_spinlock_lock(&mutex);
/*
* Critical section.
*/
ck_spinlock_unlock(&mutex);
ck_spinlock_lock_eb(&mutex);
/*
* Critical section.
*/
ck_spinlock_unlock(&mutex);
if (ck_spinlock_trylock(&mutex) == true) {
/*
* Critical section.
*/
ck_spinlock_unlock(&mutex);
}
}
.Ed
.Sh SEE ALSO
.Xr ck_cohort 3 ,
.Xr ck_elide 3
.Pp
Additional information available at http://concurrencykit.org/
|
