1 /*
2 * Copyright 2011-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_RWLOCK_H
28 #define CK_RWLOCK_H
29
30 #include <ck_elide.h>
31 #include <ck_pr.h>
32 #include <ck_stdbool.h>
33 #include <ck_stddef.h>
34
35 struct ck_rwlock {
36 unsigned int writer;
37 unsigned int n_readers;
38 };
39 typedef struct ck_rwlock ck_rwlock_t;
40
41 #define CK_RWLOCK_INITIALIZER {0, 0}
42
43 CK_CC_INLINE static void
ck_rwlock_init(struct ck_rwlock * rw)44 ck_rwlock_init(struct ck_rwlock *rw)
45 {
46
47 rw->writer = 0;
48 rw->n_readers = 0;
49 ck_pr_barrier();
50 return;
51 }
52
53 CK_CC_INLINE static void
ck_rwlock_write_unlock(ck_rwlock_t * rw)54 ck_rwlock_write_unlock(ck_rwlock_t *rw)
55 {
56
57 ck_pr_fence_unlock();
58 ck_pr_store_uint(&rw->writer, 0);
59 return;
60 }
61
62 CK_CC_INLINE static bool
ck_rwlock_locked_writer(ck_rwlock_t * rw)63 ck_rwlock_locked_writer(ck_rwlock_t *rw)
64 {
65 bool r;
66
67 r = ck_pr_load_uint(&rw->writer);
68 ck_pr_fence_acquire();
69 return r;
70 }
71
72 CK_CC_INLINE static void
ck_rwlock_write_downgrade(ck_rwlock_t * rw)73 ck_rwlock_write_downgrade(ck_rwlock_t *rw)
74 {
75
76 ck_pr_inc_uint(&rw->n_readers);
77 ck_rwlock_write_unlock(rw);
78 return;
79 }
80
81 CK_CC_INLINE static bool
ck_rwlock_locked(ck_rwlock_t * rw)82 ck_rwlock_locked(ck_rwlock_t *rw)
83 {
84 bool l;
85
86 l = ck_pr_load_uint(&rw->n_readers) |
87 ck_pr_load_uint(&rw->writer);
88 ck_pr_fence_acquire();
89 return l;
90 }
91
92 CK_CC_INLINE static bool
ck_rwlock_write_trylock(ck_rwlock_t * rw)93 ck_rwlock_write_trylock(ck_rwlock_t *rw)
94 {
95
96 if (ck_pr_fas_uint(&rw->writer, 1) != 0)
97 return false;
98
99 ck_pr_fence_atomic_load();
100
101 if (ck_pr_load_uint(&rw->n_readers) != 0) {
102 ck_rwlock_write_unlock(rw);
103 return false;
104 }
105
106 ck_pr_fence_lock();
107 return true;
108 }
109
CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_write,ck_rwlock_t,ck_rwlock_locked,ck_rwlock_write_trylock)110 CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_write, ck_rwlock_t,
111 ck_rwlock_locked, ck_rwlock_write_trylock)
112
113 CK_CC_INLINE static void
114 ck_rwlock_write_lock(ck_rwlock_t *rw)
115 {
116
117 while (ck_pr_fas_uint(&rw->writer, 1) != 0)
118 ck_pr_stall();
119
120 ck_pr_fence_atomic_load();
121
122 while (ck_pr_load_uint(&rw->n_readers) != 0)
123 ck_pr_stall();
124
125 ck_pr_fence_lock();
126 return;
127 }
128
CK_ELIDE_PROTOTYPE(ck_rwlock_write,ck_rwlock_t,ck_rwlock_locked,ck_rwlock_write_lock,ck_rwlock_locked_writer,ck_rwlock_write_unlock)129 CK_ELIDE_PROTOTYPE(ck_rwlock_write, ck_rwlock_t,
130 ck_rwlock_locked, ck_rwlock_write_lock,
131 ck_rwlock_locked_writer, ck_rwlock_write_unlock)
132
133 CK_CC_INLINE static bool
134 ck_rwlock_read_trylock(ck_rwlock_t *rw)
135 {
136
137 if (ck_pr_load_uint(&rw->writer) != 0)
138 return false;
139
140 ck_pr_inc_uint(&rw->n_readers);
141
142 /*
143 * Serialize with respect to concurrent write
144 * lock operation.
145 */
146 ck_pr_fence_atomic_load();
147
148 if (ck_pr_load_uint(&rw->writer) == 0) {
149 ck_pr_fence_lock();
150 return true;
151 }
152
153 ck_pr_dec_uint(&rw->n_readers);
154 return false;
155 }
156
CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_read,ck_rwlock_t,ck_rwlock_locked_writer,ck_rwlock_read_trylock)157 CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_read, ck_rwlock_t,
158 ck_rwlock_locked_writer, ck_rwlock_read_trylock)
159
160 CK_CC_INLINE static void
161 ck_rwlock_read_lock(ck_rwlock_t *rw)
162 {
163
164 for (;;) {
165 while (ck_pr_load_uint(&rw->writer) != 0)
166 ck_pr_stall();
167
168 ck_pr_inc_uint(&rw->n_readers);
169
170 /*
171 * Serialize with respect to concurrent write
172 * lock operation.
173 */
174 ck_pr_fence_atomic_load();
175
176 if (ck_pr_load_uint(&rw->writer) == 0)
177 break;
178
179 ck_pr_dec_uint(&rw->n_readers);
180 }
181
182 /* Acquire semantics are necessary. */
183 ck_pr_fence_load();
184 return;
185 }
186
187 CK_CC_INLINE static bool
ck_rwlock_locked_reader(ck_rwlock_t * rw)188 ck_rwlock_locked_reader(ck_rwlock_t *rw)
189 {
190
191 ck_pr_fence_load();
192 return ck_pr_load_uint(&rw->n_readers);
193 }
194
195 CK_CC_INLINE static void
ck_rwlock_read_unlock(ck_rwlock_t * rw)196 ck_rwlock_read_unlock(ck_rwlock_t *rw)
197 {
198
199 ck_pr_fence_load_atomic();
200 ck_pr_dec_uint(&rw->n_readers);
201 return;
202 }
203
204 CK_ELIDE_PROTOTYPE(ck_rwlock_read, ck_rwlock_t,
205 ck_rwlock_locked_writer, ck_rwlock_read_lock,
206 ck_rwlock_locked_reader, ck_rwlock_read_unlock)
207
208 /*
209 * Recursive writer reader-writer lock implementation.
210 */
211 struct ck_rwlock_recursive {
212 struct ck_rwlock rw;
213 unsigned int wc;
214 };
215 typedef struct ck_rwlock_recursive ck_rwlock_recursive_t;
216
217 #define CK_RWLOCK_RECURSIVE_INITIALIZER {CK_RWLOCK_INITIALIZER, 0}
218
219 CK_CC_INLINE static void
ck_rwlock_recursive_write_lock(ck_rwlock_recursive_t * rw,unsigned int tid)220 ck_rwlock_recursive_write_lock(ck_rwlock_recursive_t *rw, unsigned int tid)
221 {
222 unsigned int o;
223
224 o = ck_pr_load_uint(&rw->rw.writer);
225 if (o == tid)
226 goto leave;
227
228 while (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false)
229 ck_pr_stall();
230
231 ck_pr_fence_atomic_load();
232
233 while (ck_pr_load_uint(&rw->rw.n_readers) != 0)
234 ck_pr_stall();
235
236 ck_pr_fence_lock();
237 leave:
238 rw->wc++;
239 return;
240 }
241
242 CK_CC_INLINE static bool
ck_rwlock_recursive_write_trylock(ck_rwlock_recursive_t * rw,unsigned int tid)243 ck_rwlock_recursive_write_trylock(ck_rwlock_recursive_t *rw, unsigned int tid)
244 {
245 unsigned int o;
246
247 o = ck_pr_load_uint(&rw->rw.writer);
248 if (o == tid)
249 goto leave;
250
251 if (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false)
252 return false;
253
254 ck_pr_fence_atomic_load();
255
256 if (ck_pr_load_uint(&rw->rw.n_readers) != 0) {
257 ck_pr_store_uint(&rw->rw.writer, 0);
258 return false;
259 }
260
261 ck_pr_fence_lock();
262 leave:
263 rw->wc++;
264 return true;
265 }
266
267 CK_CC_INLINE static void
ck_rwlock_recursive_write_unlock(ck_rwlock_recursive_t * rw)268 ck_rwlock_recursive_write_unlock(ck_rwlock_recursive_t *rw)
269 {
270
271 if (--rw->wc == 0) {
272 ck_pr_fence_unlock();
273 ck_pr_store_uint(&rw->rw.writer, 0);
274 }
275
276 return;
277 }
278
279 CK_CC_INLINE static void
ck_rwlock_recursive_read_lock(ck_rwlock_recursive_t * rw)280 ck_rwlock_recursive_read_lock(ck_rwlock_recursive_t *rw)
281 {
282
283 ck_rwlock_read_lock(&rw->rw);
284 return;
285 }
286
287 CK_CC_INLINE static bool
ck_rwlock_recursive_read_trylock(ck_rwlock_recursive_t * rw)288 ck_rwlock_recursive_read_trylock(ck_rwlock_recursive_t *rw)
289 {
290
291 return ck_rwlock_read_trylock(&rw->rw);
292 }
293
294 CK_CC_INLINE static void
ck_rwlock_recursive_read_unlock(ck_rwlock_recursive_t * rw)295 ck_rwlock_recursive_read_unlock(ck_rwlock_recursive_t *rw)
296 {
297
298 ck_rwlock_read_unlock(&rw->rw);
299 return;
300 }
301
302 #endif /* CK_RWLOCK_H */
303