1ck_spinlock(3) BSD Library Functions Manual ck_spinlock(3)
2
4 ck_spinlock_init, ck_spinlock_lock, ck_spinlock_unlock,
5 ck_spinlock_locked, ck_spinlock_trylock, ck_spinlock_anderson_init,
6 ck_spinlock_anderson_locked, ck_spinlock_anderson_lock,
7 ck_spinlock_anderson_unlock, ck_spinlock_cas_init,
8 ck_spinlock_cas_locked, ck_spinlock_cas_lock, ck_spinlock_cas_lock_eb,
9 ck_spinlock_cas_trylock, ck_spinlock_cas_unlock, ck_spinlock_clh_init,
10 ck_spinlock_clh_locked, ck_spinlock_clh_lock, ck_spinlock_clh_unlock,
11 ck_spinlock_dec_init, ck_spinlock_dec_locked, ck_spinlock_dec_lock,
12 ck_spinlock_dec_lock_eb, ck_spinlock_dec_trylock, ck_spinlock_dec_unlock,
13 ck_spinlock_fas_init, ck_spinlock_fas_lock, ck_spinlock_fas_lock_eb,
14 ck_spinlock_fas_locked, ck_spinlock_fas_trylock, ck_spinlock_fas_unlock,
15 ck_spinlock_hclh_init, ck_spinlock_hclh_locked, ck_spinlock_hclh_lock,
16 ck_spinlock_hclh_unlock, ck_spinlock_mcs_init, ck_spinlock_mcs_locked,
17 ck_spinlock_mcs_lock, ck_spinlock_mcs_trylock, ck_spinlock_mcs_unlock,
18 ck_spinlock_ticket_init, ck_spinlock_ticket_locked,
19 ck_spinlock_ticket_lock, ck_spinlock_ticket_lock_pb,
20 ck_spinlock_ticket_trylock, ck_spinlock_ticket_unlock — spinlock imple‐
21 mentations
22
24 Concurrency Kit (libck, -lck)
25
27 #include <ck_spinlock.h>
28 ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;
30 void
32 ck_spinlock_init(ck_spinlock_t *lock);
33 void
35 ck_spinlock_lock(ck_spinlock_t *lock);
36 void
38 ck_spinlock_unlock(ck_spinlock_t *lock);
39 bool
41 ck_spinlock_locked(ck_spinlock_t *lock);
42 bool
44 ck_spinlock_trylock(ck_spinlock_t *lock);
45 void
47 ck_spinlock_anderson_init(ck_spinlock_anderson_t *lock,
48 ck_spinlock_anderson_thread_t *slots, unsigned int count);
49 bool
51 ck_spinlock_anderson_locked(ck_spinlock_anderson_t *lock);
52 void
54 ck_spinlock_anderson_lock(ck_spinlock_anderson_t *lock,
55 ck_spinlock_anderson_thread_t **slot);
56 void
58 ck_spinlock_anderson_unlock(ck_spinlock_anderson_t *lock,
59 ck_spinlock_anderson_thread_t *slot);
60 ck_spinlock_cas_t spinlock = CK_SPINLOCK_CAS_INITIALIZER;
62 void
64 ck_spinlock_cas_init(ck_spinlock_cas_t *lock);
65 bool
67 ck_spinlock_cas_locked(ck_spinlock_cas_t *lock);
68 void
70 ck_spinlock_cas_lock(ck_spinlock_cas_t *lock);
71 void
73 ck_spinlock_cas_lock_eb(ck_spinlock_cas_t *lock);
74 bool
76 ck_spinlock_cas_trylock(ck_spinlock_cas_t *lock);
77 void
79 ck_spinlock_cas_unlock(ck_spinlock_cas_t *lock);
80 void
82 ck_spinlock_clh_init(ck_spinlock_clh_t **lock,
83 ck_spinlock_clh_t *unowned);
84 bool
86 ck_spinlock_clh_locked(ck_spinlock_clh_t **lock);
87 void
89 ck_spinlock_clh_lock(ck_spinlock_clh_t **lock, ck_spinlock_clh_t *node);
90 void
92 ck_spinlock_clh_unlock(ck_spinlock_clh_t **node);
93 ck_spinlock_dec_t spinlock = CK_SPINLOCK_DEC_INITIALIZER;
95 void
97 ck_spinlock_dec_init(ck_spinlock_dec_t *lock);
98 bool
100 ck_spinlock_dec_locked(ck_spinlock_dec_t *lock);
101 void
103 ck_spinlock_dec_lock(ck_spinlock_dec_t *lock);
104 void
106 ck_spinlock_dec_lock_eb(ck_spinlock_dec_t *lock);
107 bool
109 ck_spinlock_dec_trylock(ck_spinlock_dec_t *lock);
110 void
112 ck_spinlock_dec_unlock(ck_spinlock_dec_t *lock);
113 ck_spinlock_fas_t spinlock = CK_SPINLOCK_FAS_INITIALIZER;
115 void
117 ck_spinlock_fas_init(ck_spinlock_fas_t *lock);
118 void
120 ck_spinlock_fas_lock(ck_spinlock_fas_t *lock);
121 void
123 ck_spinlock_fas_lock_eb(ck_spinlock_fas_t *lock);
124 bool
126 ck_spinlock_fas_locked(ck_spinlock_fas_t *lock);
127 bool
129 ck_spinlock_fas_trylock(ck_spinlock_fas_t *lock);
130 void
132 ck_spinlock_fas_unlock(ck_spinlock_fas_t *lock);
133 void
135 ck_spinlock_hclh_init(ck_spinlock_hclh_t **lock,
136 ck_spinlock_hclh_t *unowned);
137 bool
139 ck_spinlock_hclh_locked(ck_spinlock_hclh_t **lock);
140 void
142 ck_spinlock_hclh_lock(ck_spinlock_hclh_t **lock,
143 ck_spinlock_hclh_t *node);
144 void
146 ck_spinlock_hclh_unlock(ck_spinlock_hclh_t **node);
147 ck_spinlock_mcs_t spinlock = CK_SPINLOCK_MCS_INITIALIZER;
149 void
151 ck_spinlock_mcs_init(ck_spinlock_mcs_t **lock);
152 bool
154 ck_spinlock_mcs_locked(ck_spinlock_mcs_t **lock);
155 void
157 ck_spinlock_mcs_lock(ck_spinlock_mcs_t **lock, ck_spinlock_mcs_t *node);
158 bool
160 ck_spinlock_mcs_trylock(ck_spinlock_mcs_t **lock,
161 ck_spinlock_mcs_t *node);
162 void
164 ck_spinlock_mcs_unlock(ck_spinlock_mcs_t **lock,
165 ck_spinlock_mcs_t *node);
166 ck_spinlock_ticket_t spinlock = CK_SPINLOCK_TICKET_INITIALIZER;
168 void
170 ck_spinlock_ticket_init(ck_spinlock_ticket_t *lock);
171 bool
173 ck_spinlock_ticket_locked(ck_spinlock_ticket_t *lock);
174 void
176 ck_spinlock_ticket_lock(ck_spinlock_ticket_t *lock);
177 void
179 ck_spinlock_ticket_lock_pb(ck_spinlock_ticket_t *lock,
180 unsigned int period);
181 bool
183 ck_spinlock_ticket_trylock(ck_spinlock_ticket_t *lock);
184 void
186 ck_spinlock_ticket_unlock(ck_spinlock_ticket_t *lock);
187
189 A family of busy-wait spinlock implementations. The ck_spinlock_t imple‐
190 mentation is simply a wrapper around the fetch-and-swap (ck_spin‐
191 lock_fas_t) implementation. The table below provides a summary of the
192 current implementations.
193 | Namespace | Algorithm | Type | Restrictions | Fair |
195 ´----------------------|-----------------------------|---------------|-------------------------|--------'
196 ck_spinlock_anderson Anderson Array Fixed number of threads Yes
197 ck_spinlock_cas Compare-and-Swap Centralized None No
198 ck_spinlock_clh Craig, Landin and Hagersten Queue Lifetime requirements Yes
199 ck_spinlock_dec Decrement (Linux kernel) Centralized UINT_MAX concurrency No
200 ck_spinlock_fas Fetch-and-store Centralized None No
201 ck_spinlock_hclh Hierarchical CLH Queue Lifetime requirements Yes *
202 ck_spinlock_mcs Mellor-Crummey and Scott Queue None Yes
203 ck_spinlock_ticket Ticket Centralized None Yes
204 * Hierarchical CLH only offers weak fairness for threads accross cluster
206 nodes.
207 If contention is low and there is no hard requirement for starvation-
209 freedom then a centralized greedy (unfair) spinlock is recommended. If
210 contention is high and there is no requirement for starvation-freedom
211 then a centralized greedy spinlock is recommended to be used with an
212 exponential backoff mechanism. If contention is generally low and there
213 is a hard requirement for starvation-freedom then the ticket lock is rec‐
214 ommended. If contention is high and there is a hard requirement for star‐
215 vation-freedom then the Craig and Landin and Hagersten queue spinlock is
216 recommended unless stack allocation is necessary or NUMA factor is high,
217 in which case the Mellor-Crummey and Scott spinlock is recommended. If
218 you cannot afford O(n) space-usage from array or queue spinlocks but
219 still require fairness under high contention then the ticket lock with
220 proportional back-off is recommended. If NUMA factor is high but prefer
221 a greedy lock, then please see ck_cohort(3).
222
224 #include <ck_spinlock.h>
225 #include <stdbool.h>
226 /*
228 * Alternatively, the mutex may be initialized at run-time with
229 * ck_spinlock_init(&mutex).
230 */
231 ck_spinlock_t mutex = CK_SPINLOCK_INITIALIZER;
232 void
234 example(void)
235 {
236 ck_spinlock_lock(&mutex);
238 /*
239 * Critical section.
240 */
241 ck_spinlock_unlock(&mutex);
242 ck_spinlock_lock_eb(&mutex);
244 /*
245 * Critical section.
246 */
247 ck_spinlock_unlock(&mutex);
248 if (ck_spinlock_trylock(&mutex) == true) {
250 /*
251 * Critical section.
252 */
253 ck_spinlock_unlock(&mutex);
254 }
255 }
256
258 ck_cohort(3), ck_elide(3)
259 Additional information available at http://concurrencykit.org/
261 July 26, 2013.