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