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
|
.\"
.\" 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 13, 2013.
.Dt ck_elide 3
.Sh NAME
.Nm CK_ELIDE_PROTOTYPE ,
.Nm CK_ELIDE_LOCK_ADAPTIVE ,
.Nm CK_ELIDE_UNLOCK_ADAPTIVE ,
.Nm CK_ELIDE_LOCK ,
.Nm CK_ELIDE_UNLOCK ,
.Nm CK_ELIDE_TRYLOCK_PROTOTYPE ,
.Nm CK_ELIDE_TRYLOCK
.Nd lock elision wrappers
.Sh LIBRARY
Concurrency Kit (libck, \-lck)
.Sh SYNOPSIS
.In ck_elide.h
.Pp
.Dv ck_elide_stat_t stat = CK_ELIDE_STAT_INITIALIZER;
.Pp
.Ft void
.Fn ck_elide_stat_init "ck_elide_stat_t *"
.Pp
.Dv struct ck_elide_config config = CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
.Pp
.Bd -literal -offset
struct ck_elide_config {
unsigned short skip_busy;
short retry_busy;
unsigned short skip_other;
short retry_other;
unsigned short skip_conflict;
short retry_conflict;
};
.Ed
.Pp
.Fn CK_ELIDE_PROTOTYPE "NAME" "TYPE" "LOCK_PREDICATE" "LOCK_FUNCTION" "UNLOCK_PREDICATE" "UNLOCK_FUNCTION"
.Fn CK_ELIDE_LOCK_ADAPTIVE "NAME" "ck_elide_stat_t *" "struct ck_elide_config *" "TYPE *"
.Fn CK_ELIDE_UNLOCK_ADAPTIVE "NAME" "ck_elide_stat_t *" "TYPE *"
.Fn CK_ELIDE_LOCK "NAME" "TYPE *"
.Fn CK_ELIDE_UNLOCK "NAME" "TYPE *"
.Fn CK_ELIDE_TRYLOCK_PROTOTYPE "NAME" "TYPE" "LOCK_PREDICATE" "TRYLOCK_FUNCTION"
.Sh DESCRIPTION
These macros implement lock elision wrappers for a user-specified single-argument
lock interface. The wrappers will attempt to elide lock acquisition, allowing
concurrent execution of critical sections that do not issue conflicting memory
operations. If any threads have successfully elided a lock acquisition,
conflicting memory operations will roll-back any side-effects of the critical
section and force every thread to retry the lock acquisition regularly.
.Pp
.Fn CK_ELIDE_LOCK ,
.Fn CK_ELIDE_UNLOCK ,
.Fn CK_ELIDE_LOCK_ADAPTIVE ,
and
.Fn CK_ELIDE_UNLOCK_ADAPTIVE
macros require
a previous
.Fn CK_ELIDE_PROTOTYPE
with the same
.Fa NAME .
Elision is attempted if the
.Fa LOCK_PREDICATE
function returns false. If
.Fa LOCK_PREDICATE
returns true then elision is aborted and
.Fa LOCK_FUNCTION
is executed instead. If any threads are in an elided critical section,
.Fa LOCK_FUNCTION
must force them to rollback through a conflicting memory operation.
The
.Fa UNLOCK_PREDICATE
function must return true if the lock is acquired by the caller, meaning
that the lock was not successfully elided. If
.Fa UNLOCK_PREDICATE
returns true, then the
.Fa UNLOCK_FUNCTION
is executed. If RTM is unsupported (no CK_F_PR_RTM macro) then
.Fn CK_ELIDE_LOCK
and
.Fn CK_ELIDE_LOCK_ADAPTIVE
will immediately call
.Fn LOCK_FUNCTION .
.Fn CK_ELIDE_UNLOCK
and
.Fn CK_ELIDE_UNLOCK_ADAPTIVE
will immediately call
.Fn UNLOCK_FUNCTION .
.Pp
.Fn CK_ELIDE_TRYLOCK
requires a previous
.Fn CK_ELIDE_TRYLOCK_PROTOTYPE
with the same name.
Elision is attempted if the
.Fa LOCK_PREDICATE
function returns false. If
.Fa LOCK_PREDICATE
returns true or if elision fails then the
operation is aborted. If RTM is unsupported
(no CK_F_PR_RTM macro) then
.Fn CK_ELIDE_TRYLOCK
will immediately call
.Fn TRYLOCK_FUNCTION .
.Pp
.Fn CK_ELIDE_LOCK_ADAPTIVE
and
.Fn CK_ELIDE_UNLOCK_ADAPTIVE
will adapt the elision behavior associated with lock operations
according to the run-time behavior of the program. This behavior
is defined by the ck_elide_config structure pointer passed to
.Fn CK_ELIDE_LOCK_ADAPTIVE .
A thread-local ck_elide_stat structure must be passed to both
.Fn CK_ELIDE_LOCK_ADAPTIVE
and
.Fn CK_ELIDE_UNLOCK_ADAPTIVE .
This structure is expected to be unique for different workloads,
may not be re-used in recursive acquisitions and must match the
lifetime of the lock it is associated with. It is safe to mix
adaptive calls with best-effort calls.
.Pp
Both ck_spinlock.h and ck_rwlock.h define ck_elide wrappers under
the ck_spinlock and ck_rwlock namespace, respectively.
.Sh EXAMPLES
This example utilizes built-in lock elision facilities in ck_rwlock and ck_spinlock.
.Bd -literal -offset indent
#include <ck_rwlock.h>
#include <ck_spinlock.h>
static ck_rwlock_t rw = CK_RWLOCK_INITIALIZER;
static struct ck_elide_config rw_config =
CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
static __thread ck_elide_stat_t rw_stat =
CK_ELIDE_STAT_INITIALIZER;
static ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;
static struct ck_elide_config spinlock_config =
CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
static __thread ck_elide_stat_t spinlock_stat =
CK_ELIDE_STAT_INITIALIZER;
void
function(void)
{
/* Lock-unlock write-side lock in weak best-effort manner. */
CK_ELIDE_LOCK(ck_rwlock_write, &rw);
CK_ELIDE_UNLOCK(ck_rwlock_write, &rw);
/* Attempt to acquire the write-side lock. */
if (CK_ELIDE_TRYLOCK(ck_rwlock_write, &rw) == true)
CK_ELIDE_UNLOCK(ck_rwlock_write, &rw);
/* Lock-unlock read-side lock in weak best-effort manner. */
CK_ELIDE_LOCK(ck_rwlock_read, &rw);
CK_ELIDE_UNLOCK(ck_rwlock_read, &rw);
/* Attempt to acquire the read-side lock. */
if (CK_ELIDE_TRYLOCK(ck_rwlock_read, &rw) == true)
CK_ELIDE_UNLOCK(ck_rwlock_read, &rw);
/* Lock-unlock write-side lock in an adaptive manner. */
CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_write, &rw_stat,
&rw_config, &rw);
CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_write, &rw_stat,
&rw_config, &rw);
/* Lock-unlock read-side lock in an adaptive manner. */
CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_read, &rw_stat,
&rw_config, &rw);
CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_read, &rw_stat,
&rw_config, &rw);
/* Lock-unlock spinlock in weak best-effort manner. */
CK_ELIDE_LOCK(ck_spinlock, &spinlock);
CK_ELIDE_UNLOCK(ck_spinlock, &spinlock);
/* Attempt to acquire the lock. */
if (CK_ELIDE_TRYLOCK(ck_spinlock, &lock) == true)
CK_ELIDE_UNLOCK(ck_spinlock, &spinlock);
/* Lock-unlock spinlock in an adaptive manner. */
CK_ELIDE_LOCK_ADAPTIVE(ck_spinlock, &spinlock_stat,
&spinlock_config, &spinlock);
CK_ELIDE_UNLOCK_ADAPTIVE(ck_spinlock, &spinlock_stat,
&spinlock_config, &spinlock);
}
.Ed
.Pp
In this example, user-defined locking functions are provided an elision
implementation.
.Bd -literal -offset indent
/* Assume lock_t has been previously defined. */
#include <ck_elide.h>
/*
* This function returns true if the lock is unavailable at the time
* it was called or false if the lock is available.
*/
bool is_locked(lock_t *);
/*
* This function acquires the supplied lock.
*/
void lock(lock_t *);
/*
* This function releases the lock.
*/
void unlock(lock_t *);
CK_ELIDE_PROTOTYPE(my_lock, lock_t, is_locked, lock, is_locked, unlock)
static lock_t lock;
void
function(void)
{
CK_ELIDE_LOCK(my_lock, &lock);
CK_ELIDE_UNLOCK(my_lock, &lock);
}
.Ed
.Sh SEE ALSO
.Xr ck_rwlock 3 ,
.Xr ck_spinlock 3
.Pp
Ravi Rajwar and James R. Goodman. 2001. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture (MICRO 34). IEEE Computer Society, Washington, DC, USA, 294-305.
.Pp
Additional information available at http://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions and http://concurrencykit.org/
|
