]>
Commit | Line | Data |
---|---|---|
440d5faa DL |
1 | /* |
2 | * "Sequence" lock primitive | |
3 | * | |
4 | * Copyright (C) 2015 David Lamparter <equinox@diac24.net> | |
5 | * | |
6 | * This library is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU Lesser General Public | |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2.1 of the License, or (at your option) any later version. | |
10 | * | |
11 | * This library is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * Lesser General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU Lesser General Public | |
17 | * License along with this library; if not, write to the | |
18 | * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
19 | * Boston, MA 02110-1301 USA | |
20 | */ | |
21 | ||
22 | #define _GNU_SOURCE | |
23 | ||
24 | #ifdef HAVE_CONFIG_H | |
25 | #include "config.h" | |
26 | #endif | |
27 | ||
2a5e6235 | 28 | #include <string.h> |
440d5faa DL |
29 | #include <unistd.h> |
30 | #include <limits.h> | |
31 | #include <errno.h> | |
32 | #include <sys/types.h> | |
33 | #include <sys/time.h> | |
34 | #include <pthread.h> | |
35 | #include <assert.h> | |
36 | ||
37 | #include "seqlock.h" | |
38 | ||
30ef834a DL |
39 | /**************************************** |
40 | * OS specific synchronization wrappers * | |
41 | ****************************************/ | |
42 | ||
43 | /* | |
44 | * Linux: sys_futex() | |
45 | */ | |
440d5faa | 46 | #ifdef HAVE_SYNC_LINUX_FUTEX |
440d5faa DL |
47 | #include <sys/syscall.h> |
48 | #include <linux/futex.h> | |
49 | ||
2a5e6235 DL |
50 | static long sys_futex(void *addr1, int op, int val1, |
51 | const struct timespec *timeout, void *addr2, int val3) | |
440d5faa DL |
52 | { |
53 | return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3); | |
54 | } | |
55 | ||
56 | #define wait_once(sqlo, val) \ | |
57 | sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0) | |
2a5e6235 DL |
58 | #define wait_time(sqlo, val, time, reltime) \ |
59 | sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \ | |
60 | NULL, ~0U) | |
440d5faa DL |
61 | #define wait_poke(sqlo) \ |
62 | sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0) | |
63 | ||
30ef834a DL |
64 | /* |
65 | * OpenBSD: sys_futex(), almost the same as on Linux | |
66 | */ | |
440d5faa | 67 | #elif defined(HAVE_SYNC_OPENBSD_FUTEX) |
440d5faa DL |
68 | #include <sys/syscall.h> |
69 | #include <sys/futex.h> | |
70 | ||
2a5e6235 DL |
71 | #define TIME_RELATIVE 1 |
72 | ||
440d5faa DL |
73 | #define wait_once(sqlo, val) \ |
74 | futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0) | |
2a5e6235 DL |
75 | #define wait_time(sqlo, val, time, reltime) \ |
76 | futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0) | |
440d5faa DL |
77 | #define wait_poke(sqlo) \ |
78 | futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0) | |
79 | ||
30ef834a DL |
80 | /* |
81 | * FreeBSD: _umtx_op() | |
82 | */ | |
440d5faa | 83 | #elif defined(HAVE_SYNC_UMTX_OP) |
440d5faa DL |
84 | #include <sys/umtx.h> |
85 | ||
86 | #define wait_once(sqlo, val) \ | |
87 | _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, NULL, NULL) | |
2a5e6235 DL |
88 | static int wait_time(struct seqlock *sqlo, uint32_t val, |
89 | const struct timespec *abstime, | |
90 | const struct timespec *reltime) | |
91 | { | |
92 | struct _umtx_time t; | |
93 | t._flags = UMTX_ABSTIME; | |
94 | t._clockid = CLOCK_MONOTONIC; | |
95 | memcpy(&t._timeout, abstime, sizeof(t._timeout)); | |
96 | return _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, | |
97 | (void *)(uintptr_t) sizeof(t), &t); | |
98 | } | |
440d5faa DL |
99 | #define wait_poke(sqlo) \ |
100 | _umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL) | |
101 | ||
30ef834a DL |
102 | /* |
103 | * generic version. used on NetBSD, Solaris and OSX. really shitty. | |
440d5faa | 104 | */ |
30ef834a | 105 | #else |
440d5faa | 106 | |
2a5e6235 DL |
107 | #define TIME_ABS_REALTIME 1 |
108 | ||
440d5faa DL |
109 | #define wait_init(sqlo) do { \ |
110 | pthread_mutex_init(&sqlo->lock, NULL); \ | |
111 | pthread_cond_init(&sqlo->wake, NULL); \ | |
112 | } while (0) | |
113 | #define wait_prep(sqlo) pthread_mutex_lock(&sqlo->lock) | |
114 | #define wait_once(sqlo, val) pthread_cond_wait(&sqlo->wake, &sqlo->lock) | |
2a5e6235 DL |
115 | #define wait_time(sqlo, val, time, reltime) \ |
116 | pthread_cond_timedwait(&sqlo->wake, \ | |
117 | &sqlo->lock, time); | |
440d5faa DL |
118 | #define wait_done(sqlo) pthread_mutex_unlock(&sqlo->lock) |
119 | #define wait_poke(sqlo) do { \ | |
120 | pthread_mutex_lock(&sqlo->lock); \ | |
121 | pthread_cond_broadcast(&sqlo->wake); \ | |
122 | pthread_mutex_unlock(&sqlo->lock); \ | |
123 | } while (0) | |
124 | ||
125 | #endif | |
126 | ||
127 | #ifndef wait_init | |
128 | #define wait_init(sqlo) /**/ | |
129 | #define wait_prep(sqlo) /**/ | |
130 | #define wait_done(sqlo) /**/ | |
131 | #endif /* wait_init */ | |
132 | ||
133 | ||
134 | void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val) | |
135 | { | |
136 | seqlock_val_t cur, cal; | |
137 | ||
138 | seqlock_assert_valid(val); | |
139 | ||
140 | wait_prep(sqlo); | |
6046b690 DL |
141 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
142 | ||
143 | while (cur & SEQLOCK_HELD) { | |
144 | cal = SEQLOCK_VAL(cur) - val - 1; | |
440d5faa DL |
145 | assert(cal < 0x40000000 || cal > 0xc0000000); |
146 | if (cal < 0x80000000) | |
147 | break; | |
148 | ||
6046b690 DL |
149 | if ((cur & SEQLOCK_WAITERS) |
150 | || atomic_compare_exchange_weak_explicit( | |
151 | &sqlo->pos, &cur, cur | SEQLOCK_WAITERS, | |
152 | memory_order_relaxed, memory_order_relaxed)) { | |
153 | wait_once(sqlo, cur | SEQLOCK_WAITERS); | |
154 | cur = atomic_load_explicit(&sqlo->pos, | |
155 | memory_order_relaxed); | |
156 | } | |
157 | /* else: we failed to swap in cur because it just changed */ | |
440d5faa DL |
158 | } |
159 | wait_done(sqlo); | |
160 | } | |
161 | ||
2a5e6235 DL |
162 | bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val, |
163 | const struct timespec *abs_monotime_limit) | |
164 | { | |
30ef834a DL |
165 | /* |
166 | * ABS_REALTIME - used on NetBSD, Solaris and OSX | |
167 | */ | |
1e20238a | 168 | #ifdef TIME_ABS_REALTIME |
2a5e6235 DL |
169 | #define time_arg1 &abs_rt |
170 | #define time_arg2 NULL | |
171 | #define time_prep | |
172 | struct timespec curmono, abs_rt; | |
173 | ||
174 | clock_gettime(CLOCK_MONOTONIC, &curmono); | |
175 | clock_gettime(CLOCK_REALTIME, &abs_rt); | |
176 | ||
177 | abs_rt.tv_nsec += abs_monotime_limit->tv_nsec - curmono.tv_nsec; | |
178 | if (abs_rt.tv_nsec < 0) { | |
179 | abs_rt.tv_sec--; | |
180 | abs_rt.tv_nsec += 1000000000; | |
181 | } else if (abs_rt.tv_nsec >= 1000000000) { | |
182 | abs_rt.tv_sec++; | |
183 | abs_rt.tv_nsec -= 1000000000; | |
184 | } | |
185 | abs_rt.tv_sec += abs_monotime_limit->tv_sec - curmono.tv_sec; | |
186 | ||
30ef834a DL |
187 | /* |
188 | * RELATIVE - used on OpenBSD (might get a patch to get absolute monotime) | |
189 | */ | |
1e20238a | 190 | #elif defined(TIME_RELATIVE) |
2a5e6235 DL |
191 | struct timespec reltime; |
192 | ||
193 | #define time_arg1 abs_monotime_limit | |
194 | #define time_arg2 &reltime | |
195 | #define time_prep \ | |
196 | clock_gettime(CLOCK_MONOTONIC, &reltime); \ | |
197 | reltime.tv_sec = abs_monotime_limit.tv_sec - reltime.tv_sec; \ | |
198 | reltime.tv_nsec = abs_monotime_limit.tv_nsec - reltime.tv_nsec; \ | |
199 | if (reltime.tv_nsec < 0) { \ | |
200 | reltime.tv_sec--; \ | |
201 | reltime.tv_nsec += 1000000000; \ | |
202 | } | |
30ef834a DL |
203 | /* |
204 | * FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC | |
205 | */ | |
2a5e6235 DL |
206 | #else |
207 | #define time_arg1 abs_monotime_limit | |
208 | #define time_arg2 NULL | |
209 | #define time_prep | |
210 | #endif | |
211 | ||
212 | bool ret = true; | |
213 | seqlock_val_t cur, cal; | |
214 | ||
215 | seqlock_assert_valid(val); | |
216 | ||
217 | wait_prep(sqlo); | |
218 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); | |
219 | ||
220 | while (cur & SEQLOCK_HELD) { | |
221 | cal = SEQLOCK_VAL(cur) - val - 1; | |
222 | assert(cal < 0x40000000 || cal > 0xc0000000); | |
223 | if (cal < 0x80000000) | |
224 | break; | |
225 | ||
226 | if ((cur & SEQLOCK_WAITERS) | |
227 | || atomic_compare_exchange_weak_explicit( | |
228 | &sqlo->pos, &cur, cur | SEQLOCK_WAITERS, | |
229 | memory_order_relaxed, memory_order_relaxed)) { | |
230 | int rv; | |
231 | ||
232 | time_prep | |
233 | ||
234 | rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1, | |
235 | time_arg2); | |
236 | if (rv) { | |
237 | ret = false; | |
238 | break; | |
239 | } | |
240 | cur = atomic_load_explicit(&sqlo->pos, | |
241 | memory_order_relaxed); | |
242 | } | |
243 | } | |
244 | wait_done(sqlo); | |
245 | ||
246 | return ret; | |
247 | } | |
248 | ||
440d5faa DL |
249 | bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val) |
250 | { | |
251 | seqlock_val_t cur; | |
252 | ||
253 | seqlock_assert_valid(val); | |
254 | ||
6046b690 DL |
255 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
256 | if (!(cur & SEQLOCK_HELD)) | |
f06c4576 | 257 | return true; |
6046b690 | 258 | cur = SEQLOCK_VAL(cur) - val - 1; |
440d5faa DL |
259 | assert(cur < 0x40000000 || cur > 0xc0000000); |
260 | return cur < 0x80000000; | |
261 | } | |
262 | ||
263 | void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val) | |
264 | { | |
6046b690 DL |
265 | seqlock_val_t prev; |
266 | ||
440d5faa DL |
267 | seqlock_assert_valid(val); |
268 | ||
6046b690 DL |
269 | prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed); |
270 | if (prev & SEQLOCK_WAITERS) | |
271 | wait_poke(sqlo); | |
440d5faa DL |
272 | } |
273 | ||
274 | void seqlock_release(struct seqlock *sqlo) | |
275 | { | |
6046b690 DL |
276 | seqlock_val_t prev; |
277 | ||
278 | prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed); | |
279 | if (prev & SEQLOCK_WAITERS) | |
280 | wait_poke(sqlo); | |
440d5faa DL |
281 | } |
282 | ||
283 | void seqlock_init(struct seqlock *sqlo) | |
284 | { | |
285 | sqlo->pos = 0; | |
286 | wait_init(sqlo); | |
287 | } | |
288 | ||
289 | ||
290 | seqlock_val_t seqlock_cur(struct seqlock *sqlo) | |
291 | { | |
6046b690 DL |
292 | return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos, |
293 | memory_order_relaxed)); | |
440d5faa DL |
294 | } |
295 | ||
296 | seqlock_val_t seqlock_bump(struct seqlock *sqlo) | |
297 | { | |
6046b690 DL |
298 | seqlock_val_t val, cur; |
299 | ||
300 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); | |
301 | seqlock_assert_valid(cur); | |
302 | ||
303 | do { | |
304 | val = SEQLOCK_VAL(cur) + SEQLOCK_INCR; | |
305 | } while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val, | |
306 | memory_order_relaxed, memory_order_relaxed)); | |
440d5faa | 307 | |
6046b690 DL |
308 | if (cur & SEQLOCK_WAITERS) |
309 | wait_poke(sqlo); | |
440d5faa DL |
310 | return val; |
311 | } |