Line data Source code
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 :
28 : #include <string.h>
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 :
39 : /****************************************
40 : * OS specific synchronization wrappers *
41 : ****************************************/
42 :
43 : /*
44 : * Linux: sys_futex()
45 : */
46 : #ifdef HAVE_SYNC_LINUX_FUTEX
47 : #include <sys/syscall.h>
48 : #include <linux/futex.h>
49 :
50 56 : static long sys_futex(void *addr1, int op, int val1,
51 : const struct timespec *timeout, void *addr2, int val3)
52 : {
53 56 : 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)
58 : #define wait_time(sqlo, val, time, reltime) \
59 : sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \
60 : NULL, ~0U)
61 : #define wait_poke(sqlo) \
62 : sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
63 :
64 : /*
65 : * OpenBSD: sys_futex(), almost the same as on Linux
66 : */
67 : #elif defined(HAVE_SYNC_OPENBSD_FUTEX)
68 : #include <sys/syscall.h>
69 : #include <sys/futex.h>
70 :
71 : #define TIME_RELATIVE 1
72 :
73 : #define wait_once(sqlo, val) \
74 : futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
75 : #define wait_time(sqlo, val, time, reltime) \
76 : futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0)
77 : #define wait_poke(sqlo) \
78 : futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
79 :
80 : /*
81 : * FreeBSD: _umtx_op()
82 : */
83 : #elif defined(HAVE_SYNC_UMTX_OP)
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)
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 : }
99 : #define wait_poke(sqlo) \
100 : _umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)
101 :
102 : /*
103 : * generic version. used on NetBSD, Solaris and OSX. really shitty.
104 : */
105 : #else
106 :
107 : #define TIME_ABS_REALTIME 1
108 :
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)
115 : #define wait_time(sqlo, val, time, reltime) \
116 : pthread_cond_timedwait(&sqlo->wake, \
117 : &sqlo->lock, time);
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 28 : void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val)
135 : {
136 28 : seqlock_val_t cur, cal;
137 :
138 28 : seqlock_assert_valid(val);
139 :
140 28 : wait_prep(sqlo);
141 28 : cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
142 :
143 44 : while (cur & SEQLOCK_HELD) {
144 40 : cal = SEQLOCK_VAL(cur) - val - 1;
145 40 : assert(cal < 0x40000000 || cal > 0xc0000000);
146 40 : if (cal < 0x80000000)
147 : break;
148 :
149 16 : if ((cur & SEQLOCK_WAITERS)
150 16 : || atomic_compare_exchange_weak_explicit(
151 : &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
152 : memory_order_relaxed, memory_order_relaxed)) {
153 16 : wait_once(sqlo, cur | SEQLOCK_WAITERS);
154 16 : cur = atomic_load_explicit(&sqlo->pos,
155 : memory_order_relaxed);
156 : }
157 : /* else: we failed to swap in cur because it just changed */
158 : }
159 28 : wait_done(sqlo);
160 28 : }
161 :
162 64 : bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
163 : const struct timespec *abs_monotime_limit)
164 : {
165 : /*
166 : * ABS_REALTIME - used on NetBSD, Solaris and OSX
167 : */
168 : #ifdef TIME_ABS_REALTIME
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 :
187 : /*
188 : * RELATIVE - used on OpenBSD (might get a patch to get absolute monotime)
189 : */
190 : #elif defined(TIME_RELATIVE)
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 : }
203 : /*
204 : * FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC
205 : */
206 : #else
207 : #define time_arg1 abs_monotime_limit
208 : #define time_arg2 NULL
209 : #define time_prep
210 : #endif
211 :
212 64 : bool ret = true;
213 64 : seqlock_val_t cur, cal;
214 :
215 64 : seqlock_assert_valid(val);
216 :
217 64 : wait_prep(sqlo);
218 64 : cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
219 :
220 76 : while (cur & SEQLOCK_HELD) {
221 28 : cal = SEQLOCK_VAL(cur) - val - 1;
222 28 : assert(cal < 0x40000000 || cal > 0xc0000000);
223 28 : if (cal < 0x80000000)
224 : break;
225 :
226 12 : if ((cur & SEQLOCK_WAITERS)
227 12 : || atomic_compare_exchange_weak_explicit(
228 : &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
229 : memory_order_relaxed, memory_order_relaxed)) {
230 12 : int rv;
231 :
232 : time_prep
233 :
234 12 : rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1,
235 : time_arg2);
236 12 : if (rv) {
237 : ret = false;
238 : break;
239 : }
240 12 : cur = atomic_load_explicit(&sqlo->pos,
241 : memory_order_relaxed);
242 : }
243 : }
244 64 : wait_done(sqlo);
245 :
246 64 : return ret;
247 : }
248 :
249 0 : bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val)
250 : {
251 0 : seqlock_val_t cur;
252 :
253 0 : seqlock_assert_valid(val);
254 :
255 0 : cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
256 0 : if (!(cur & SEQLOCK_HELD))
257 : return true;
258 0 : cur = SEQLOCK_VAL(cur) - val - 1;
259 0 : assert(cur < 0x40000000 || cur > 0xc0000000);
260 0 : return cur < 0x80000000;
261 : }
262 :
263 42088 : void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
264 : {
265 42088 : seqlock_val_t prev;
266 :
267 42088 : seqlock_assert_valid(val);
268 :
269 42088 : prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed);
270 42088 : if (prev & SEQLOCK_WAITERS)
271 0 : wait_poke(sqlo);
272 42088 : }
273 :
274 21036 : void seqlock_release(struct seqlock *sqlo)
275 : {
276 21036 : seqlock_val_t prev;
277 :
278 21036 : prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed);
279 21036 : if (prev & SEQLOCK_WAITERS)
280 12 : wait_poke(sqlo);
281 21036 : }
282 :
283 44 : void seqlock_init(struct seqlock *sqlo)
284 : {
285 44 : sqlo->pos = 0;
286 44 : wait_init(sqlo);
287 44 : }
288 :
289 :
290 84080 : seqlock_val_t seqlock_cur(struct seqlock *sqlo)
291 : {
292 84080 : return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos,
293 : memory_order_relaxed));
294 : }
295 :
296 24 : seqlock_val_t seqlock_bump(struct seqlock *sqlo)
297 : {
298 24 : seqlock_val_t val, cur;
299 :
300 24 : cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
301 24 : seqlock_assert_valid(cur);
302 :
303 24 : do {
304 24 : val = SEQLOCK_VAL(cur) + SEQLOCK_INCR;
305 24 : } while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val,
306 : memory_order_relaxed, memory_order_relaxed));
307 :
308 24 : if (cur & SEQLOCK_WAITERS)
309 16 : wait_poke(sqlo);
310 24 : return val;
311 : }
|
