Line | Count | Source (jump to first uncovered line) |
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 | | static long sys_futex(void *addr1, int op, int val1, |
37 | | const struct timespec *timeout, void *addr2, int val3) |
38 | 0 | { |
39 | 0 | return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3); |
40 | 0 | } |
41 | | |
42 | | #define wait_once(sqlo, val) \ |
43 | 0 | sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0) |
44 | | #define wait_time(sqlo, val, time, reltime) \ |
45 | 0 | sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \ |
46 | 0 | NULL, ~0U) |
47 | | #define wait_poke(sqlo) \ |
48 | 0 | 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 | | void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val) |
121 | 0 | { |
122 | 0 | seqlock_val_t cur, cal; |
123 | |
|
124 | 0 | seqlock_assert_valid(val); |
125 | | |
126 | 0 | wait_prep(sqlo); |
127 | 0 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
128 | |
|
129 | 0 | while (cur & SEQLOCK_HELD) { |
130 | 0 | cal = SEQLOCK_VAL(cur) - val - 1; |
131 | 0 | assert(cal < 0x40000000 || cal > 0xc0000000); |
132 | 0 | if (cal < 0x80000000) |
133 | 0 | break; |
134 | | |
135 | 0 | if ((cur & SEQLOCK_WAITERS) |
136 | 0 | || atomic_compare_exchange_weak_explicit( |
137 | 0 | &sqlo->pos, &cur, cur | SEQLOCK_WAITERS, |
138 | 0 | memory_order_relaxed, memory_order_relaxed)) { |
139 | 0 | wait_once(sqlo, cur | SEQLOCK_WAITERS); |
140 | 0 | cur = atomic_load_explicit(&sqlo->pos, |
141 | 0 | memory_order_relaxed); |
142 | 0 | } |
143 | | /* else: we failed to swap in cur because it just changed */ |
144 | 0 | } |
145 | 0 | wait_done(sqlo); |
146 | 0 | } |
147 | | |
148 | | bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val, |
149 | | const struct timespec *abs_monotime_limit) |
150 | 0 | { |
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 | 0 | #define time_arg1 abs_monotime_limit |
194 | 0 | #define time_arg2 NULL |
195 | 0 | #define time_prep |
196 | 0 | #endif |
197 | |
|
198 | 0 | bool ret = true; |
199 | 0 | seqlock_val_t cur, cal; |
200 | |
|
201 | 0 | seqlock_assert_valid(val); |
202 | | |
203 | 0 | wait_prep(sqlo); |
204 | 0 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
205 | |
|
206 | 0 | while (cur & SEQLOCK_HELD) { |
207 | 0 | cal = SEQLOCK_VAL(cur) - val - 1; |
208 | 0 | assert(cal < 0x40000000 || cal > 0xc0000000); |
209 | 0 | if (cal < 0x80000000) |
210 | 0 | break; |
211 | | |
212 | 0 | if ((cur & SEQLOCK_WAITERS) |
213 | 0 | || atomic_compare_exchange_weak_explicit( |
214 | 0 | &sqlo->pos, &cur, cur | SEQLOCK_WAITERS, |
215 | 0 | memory_order_relaxed, memory_order_relaxed)) { |
216 | 0 | int rv; |
217 | | |
218 | | time_prep |
219 | |
|
220 | 0 | rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1, |
221 | 0 | time_arg2); |
222 | 0 | if (rv) { |
223 | 0 | ret = false; |
224 | 0 | break; |
225 | 0 | } |
226 | 0 | cur = atomic_load_explicit(&sqlo->pos, |
227 | 0 | memory_order_relaxed); |
228 | 0 | } |
229 | 0 | } |
230 | 0 | wait_done(sqlo); |
231 | |
|
232 | 0 | return ret; |
233 | 0 | } |
234 | | |
235 | | bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val) |
236 | 0 | { |
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 | 0 | return true; |
244 | 0 | cur = SEQLOCK_VAL(cur) - val - 1; |
245 | 0 | assert(cur < 0x40000000 || cur > 0xc0000000); |
246 | 0 | return cur < 0x80000000; |
247 | 0 | } |
248 | | |
249 | | void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val) |
250 | 12 | { |
251 | 12 | seqlock_val_t prev; |
252 | | |
253 | 12 | seqlock_assert_valid(val); |
254 | | |
255 | 12 | prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed); |
256 | 12 | if (prev & SEQLOCK_WAITERS) |
257 | 0 | wait_poke(sqlo); |
258 | 12 | } |
259 | | |
260 | | void seqlock_release(struct seqlock *sqlo) |
261 | 0 | { |
262 | 0 | seqlock_val_t prev; |
263 | |
|
264 | 0 | prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed); |
265 | 0 | if (prev & SEQLOCK_WAITERS) |
266 | 0 | wait_poke(sqlo); |
267 | 0 | } |
268 | | |
269 | | void seqlock_init(struct seqlock *sqlo) |
270 | 12 | { |
271 | 12 | sqlo->pos = 0; |
272 | 12 | wait_init(sqlo); |
273 | 12 | } |
274 | | |
275 | | |
276 | | seqlock_val_t seqlock_cur(struct seqlock *sqlo) |
277 | 0 | { |
278 | 0 | return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos, |
279 | 0 | memory_order_relaxed)); |
280 | 0 | } |
281 | | |
282 | | seqlock_val_t seqlock_bump(struct seqlock *sqlo) |
283 | 0 | { |
284 | 0 | seqlock_val_t val, cur; |
285 | |
|
286 | 0 | cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
287 | 0 | seqlock_assert_valid(cur); |
288 | | |
289 | 0 | do { |
290 | 0 | val = SEQLOCK_VAL(cur) + SEQLOCK_INCR; |
291 | 0 | } while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val, |
292 | 0 | memory_order_relaxed, memory_order_relaxed)); |
293 | |
|
294 | 0 | if (cur & SEQLOCK_WAITERS) |
295 | 0 | wait_poke(sqlo); |
296 | 0 | return val; |
297 | 0 | } |