Commit | Line | Data |
---|---|---|
9f1621ca | 1 | /* |
7ac06cef | 2 | * urcu-qsbr.c |
9f1621ca | 3 | * |
7ac06cef | 4 | * Userspace RCU QSBR library |
9f1621ca MD |
5 | * |
6 | * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca> | |
7 | * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. | |
8 | * | |
9 | * This library is free software; you can redistribute it and/or | |
10 | * modify it under the terms of the GNU Lesser General Public | |
11 | * License as published by the Free Software Foundation; either | |
12 | * version 2.1 of the License, or (at your option) any later version. | |
13 | * | |
14 | * This library is distributed in the hope that it will be useful, | |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
17 | * Lesser General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU Lesser General Public | |
20 | * License along with this library; if not, write to the Free Software | |
21 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
22 | * | |
23 | * IBM's contributions to this file may be relicensed under LGPLv2 or later. | |
24 | */ | |
25 | ||
26 | #include <stdio.h> | |
27 | #include <pthread.h> | |
28 | #include <signal.h> | |
29 | #include <assert.h> | |
30 | #include <stdlib.h> | |
31 | #include <string.h> | |
32 | #include <errno.h> | |
33 | #include <poll.h> | |
34 | ||
727f819d | 35 | #define BUILD_QSBR_LIB |
7ac06cef | 36 | #include "urcu-qsbr-static.h" |
9f1621ca | 37 | /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ |
7ac06cef | 38 | #include "urcu-qsbr.h" |
9f1621ca | 39 | |
81d1f1f5 | 40 | static pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER; |
9f1621ca | 41 | |
bc6c15bb MD |
42 | int gp_futex; |
43 | ||
9f1621ca MD |
44 | /* |
45 | * Global grace period counter. | |
46 | */ | |
ac258107 | 47 | unsigned long urcu_gp_ctr = RCU_GP_ONLINE; |
9f1621ca MD |
48 | |
49 | /* | |
50 | * Written to only by each individual reader. Read by both the reader and the | |
51 | * writers. | |
52 | */ | |
4f8e3380 | 53 | struct urcu_reader __thread urcu_reader; |
9f1621ca MD |
54 | |
55 | #ifdef DEBUG_YIELD | |
56 | unsigned int yield_active; | |
57 | unsigned int __thread rand_yield; | |
58 | #endif | |
59 | ||
4f8e3380 | 60 | static LIST_HEAD(registry); |
9f1621ca | 61 | |
90c1618a | 62 | static void internal_urcu_lock(void) |
9f1621ca MD |
63 | { |
64 | int ret; | |
65 | ||
66 | #ifndef DISTRUST_SIGNALS_EXTREME | |
67 | ret = pthread_mutex_lock(&urcu_mutex); | |
68 | if (ret) { | |
69 | perror("Error in pthread mutex lock"); | |
70 | exit(-1); | |
71 | } | |
72 | #else /* #ifndef DISTRUST_SIGNALS_EXTREME */ | |
73 | while ((ret = pthread_mutex_trylock(&urcu_mutex)) != 0) { | |
74 | if (ret != EBUSY && ret != EINTR) { | |
75 | printf("ret = %d, errno = %d\n", ret, errno); | |
76 | perror("Error in pthread mutex lock"); | |
77 | exit(-1); | |
78 | } | |
9f1621ca MD |
79 | poll(NULL,0,10); |
80 | } | |
81 | #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */ | |
82 | } | |
83 | ||
90c1618a | 84 | static void internal_urcu_unlock(void) |
9f1621ca MD |
85 | { |
86 | int ret; | |
87 | ||
88 | ret = pthread_mutex_unlock(&urcu_mutex); | |
89 | if (ret) { | |
90 | perror("Error in pthread mutex unlock"); | |
91 | exit(-1); | |
92 | } | |
93 | } | |
94 | ||
bc6c15bb MD |
95 | /* |
96 | * synchronize_rcu() waiting. Single thread. | |
97 | */ | |
4f8e3380 | 98 | static void wait_gp(struct urcu_reader *index) |
bc6c15bb | 99 | { |
ec4e58a3 | 100 | uatomic_dec(&gp_futex); |
bc6c15bb | 101 | smp_mb(); /* Write futex before read reader_gp */ |
4f8e3380 | 102 | if (!rcu_gp_ongoing(&index->ctr)) { |
bc6c15bb MD |
103 | /* Read reader_gp before write futex */ |
104 | smp_mb(); | |
105 | /* Callbacks are queued, don't wait. */ | |
ec4e58a3 | 106 | uatomic_set(&gp_futex, 0); |
bc6c15bb MD |
107 | } else { |
108 | /* Read reader_gp before read futex */ | |
109 | smp_rmb(); | |
ec4e58a3 | 110 | if (uatomic_read(&gp_futex) == -1) |
bc6c15bb MD |
111 | futex(&gp_futex, FUTEX_WAIT, -1, |
112 | NULL, NULL, 0); | |
113 | } | |
114 | } | |
115 | ||
90c1618a | 116 | static void wait_for_quiescent_state(void) |
9f1621ca | 117 | { |
4f8e3380 | 118 | struct urcu_reader *index; |
9f1621ca | 119 | |
4f8e3380 | 120 | if (list_empty(®istry)) |
9f1621ca MD |
121 | return; |
122 | /* | |
3395d46c | 123 | * Wait for each thread rcu_reader_qs_gp count to become 0. |
9f1621ca | 124 | */ |
4f8e3380 | 125 | list_for_each_entry(index, ®istry, head) { |
bc6c15bb MD |
126 | int wait_loops = 0; |
127 | ||
4f8e3380 | 128 | while (rcu_gp_ongoing(&index->ctr)) { |
bc6c15bb MD |
129 | if (wait_loops++ == RCU_QS_ACTIVE_ATTEMPTS) { |
130 | wait_gp(index); | |
131 | } else { | |
9f1621ca | 132 | #ifndef HAS_INCOHERENT_CACHES |
bc6c15bb | 133 | cpu_relax(); |
9f1621ca | 134 | #else /* #ifndef HAS_INCOHERENT_CACHES */ |
bc6c15bb | 135 | smp_mb(); |
9f1621ca | 136 | #endif /* #else #ifndef HAS_INCOHERENT_CACHES */ |
bc6c15bb MD |
137 | } |
138 | } | |
9f1621ca MD |
139 | } |
140 | } | |
141 | ||
47d2f29e MD |
142 | /* |
143 | * Using a two-subphases algorithm for architectures with smaller than 64-bit | |
144 | * long-size to ensure we do not encounter an overflow bug. | |
145 | */ | |
146 | ||
147 | #if (BITS_PER_LONG < 64) | |
148 | /* | |
149 | * called with urcu_mutex held. | |
150 | */ | |
151 | static void switch_next_urcu_qparity(void) | |
152 | { | |
153 | STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr ^ RCU_GP_CTR); | |
154 | } | |
155 | ||
156 | void synchronize_rcu(void) | |
157 | { | |
bc49c323 MD |
158 | unsigned long was_online; |
159 | ||
4f8e3380 | 160 | was_online = urcu_reader.ctr; |
bc49c323 | 161 | |
47d2f29e MD |
162 | /* All threads should read qparity before accessing data structure |
163 | * where new ptr points to. | |
164 | */ | |
165 | /* Write new ptr before changing the qparity */ | |
166 | smp_mb(); | |
167 | ||
bc49c323 MD |
168 | /* |
169 | * Mark the writer thread offline to make sure we don't wait for | |
170 | * our own quiescent state. This allows using synchronize_rcu() in | |
171 | * threads registered as readers. | |
172 | */ | |
173 | if (was_online) | |
4f8e3380 | 174 | STORE_SHARED(urcu_reader.ctr, 0); |
bc49c323 | 175 | |
47d2f29e MD |
176 | internal_urcu_lock(); |
177 | ||
178 | switch_next_urcu_qparity(); /* 0 -> 1 */ | |
179 | ||
180 | /* | |
181 | * Must commit qparity update to memory before waiting for parity | |
182 | * 0 quiescent state. Failure to do so could result in the writer | |
183 | * waiting forever while new readers are always accessing data (no | |
184 | * progress). | |
185 | * Ensured by STORE_SHARED and LOAD_SHARED. | |
186 | */ | |
187 | ||
188 | /* | |
189 | * Wait for previous parity to be empty of readers. | |
190 | */ | |
191 | wait_for_quiescent_state(); /* Wait readers in parity 0 */ | |
192 | ||
193 | /* | |
194 | * Must finish waiting for quiescent state for parity 0 before | |
195 | * committing qparity update to memory. Failure to do so could result in | |
196 | * the writer waiting forever while new readers are always accessing | |
197 | * data (no progress). | |
198 | * Ensured by STORE_SHARED and LOAD_SHARED. | |
199 | */ | |
200 | ||
201 | switch_next_urcu_qparity(); /* 1 -> 0 */ | |
202 | ||
203 | /* | |
204 | * Must commit qparity update to memory before waiting for parity | |
205 | * 1 quiescent state. Failure to do so could result in the writer | |
206 | * waiting forever while new readers are always accessing data (no | |
207 | * progress). | |
208 | * Ensured by STORE_SHARED and LOAD_SHARED. | |
209 | */ | |
210 | ||
211 | /* | |
212 | * Wait for previous parity to be empty of readers. | |
213 | */ | |
214 | wait_for_quiescent_state(); /* Wait readers in parity 1 */ | |
215 | ||
216 | internal_urcu_unlock(); | |
217 | ||
bc49c323 MD |
218 | /* |
219 | * Finish waiting for reader threads before letting the old ptr being | |
47d2f29e MD |
220 | * freed. |
221 | */ | |
bc49c323 | 222 | if (was_online) |
4f8e3380 | 223 | _STORE_SHARED(urcu_reader.ctr, LOAD_SHARED(urcu_gp_ctr)); |
47d2f29e MD |
224 | smp_mb(); |
225 | } | |
226 | #else /* !(BITS_PER_LONG < 64) */ | |
9f1621ca MD |
227 | void synchronize_rcu(void) |
228 | { | |
f0f7dbdd | 229 | unsigned long was_online; |
ff2f67a0 | 230 | |
4f8e3380 | 231 | was_online = urcu_reader.ctr; |
ff2f67a0 MD |
232 | |
233 | /* | |
234 | * Mark the writer thread offline to make sure we don't wait for | |
235 | * our own quiescent state. This allows using synchronize_rcu() in | |
236 | * threads registered as readers. | |
237 | */ | |
8f50d1ce | 238 | smp_mb(); |
ff2f67a0 | 239 | if (was_online) |
4f8e3380 | 240 | STORE_SHARED(urcu_reader.ctr, 0); |
ff2f67a0 | 241 | |
4e27f058 | 242 | internal_urcu_lock(); |
55570466 | 243 | STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr + RCU_GP_CTR); |
9f1621ca | 244 | wait_for_quiescent_state(); |
9f1621ca | 245 | internal_urcu_unlock(); |
ff2f67a0 MD |
246 | |
247 | if (was_online) | |
4f8e3380 | 248 | _STORE_SHARED(urcu_reader.ctr, LOAD_SHARED(urcu_gp_ctr)); |
8f50d1ce | 249 | smp_mb(); |
9f1621ca | 250 | } |
47d2f29e | 251 | #endif /* !(BITS_PER_LONG < 64) */ |
9f1621ca MD |
252 | |
253 | /* | |
254 | * library wrappers to be used by non-LGPL compatible source code. | |
255 | */ | |
256 | ||
257 | void rcu_read_lock(void) | |
258 | { | |
259 | _rcu_read_lock(); | |
260 | } | |
261 | ||
262 | void rcu_read_unlock(void) | |
263 | { | |
264 | _rcu_read_unlock(); | |
265 | } | |
266 | ||
267 | void *rcu_dereference(void *p) | |
268 | { | |
269 | return _rcu_dereference(p); | |
270 | } | |
271 | ||
272 | void *rcu_assign_pointer_sym(void **p, void *v) | |
273 | { | |
274 | wmb(); | |
275 | return STORE_SHARED(p, v); | |
276 | } | |
277 | ||
4d1ce26f MD |
278 | void *rcu_cmpxchg_pointer_sym(void **p, void *old, void *_new) |
279 | { | |
280 | wmb(); | |
ec4e58a3 | 281 | return uatomic_cmpxchg(p, old, _new); |
4d1ce26f MD |
282 | } |
283 | ||
9f1621ca MD |
284 | void *rcu_xchg_pointer_sym(void **p, void *v) |
285 | { | |
286 | wmb(); | |
ec4e58a3 | 287 | return uatomic_xchg(p, v); |
9f1621ca MD |
288 | } |
289 | ||
290 | void *rcu_publish_content_sym(void **p, void *v) | |
291 | { | |
292 | void *oldptr; | |
293 | ||
294 | oldptr = _rcu_xchg_pointer(p, v); | |
295 | synchronize_rcu(); | |
296 | return oldptr; | |
297 | } | |
298 | ||
7ac06cef MD |
299 | void rcu_quiescent_state(void) |
300 | { | |
301 | _rcu_quiescent_state(); | |
302 | } | |
303 | ||
304 | void rcu_thread_offline(void) | |
305 | { | |
306 | _rcu_thread_offline(); | |
307 | } | |
308 | ||
309 | void rcu_thread_online(void) | |
310 | { | |
311 | _rcu_thread_online(); | |
312 | } | |
313 | ||
9f1621ca MD |
314 | void rcu_register_thread(void) |
315 | { | |
4f8e3380 MD |
316 | urcu_reader.tid = pthread_self(); |
317 | assert(urcu_reader.ctr == 0); | |
318 | ||
9f1621ca | 319 | internal_urcu_lock(); |
4f8e3380 | 320 | list_add(&urcu_reader.head, ®istry); |
9f1621ca | 321 | internal_urcu_unlock(); |
5f373c84 | 322 | _rcu_thread_online(); |
9f1621ca MD |
323 | } |
324 | ||
325 | void rcu_unregister_thread(void) | |
326 | { | |
76f3022f MD |
327 | /* |
328 | * We have to make the thread offline otherwise we end up dealocking | |
329 | * with a waiting writer. | |
330 | */ | |
331 | _rcu_thread_offline(); | |
9f1621ca | 332 | internal_urcu_lock(); |
4f8e3380 | 333 | list_del(&urcu_reader.head); |
9f1621ca MD |
334 | internal_urcu_unlock(); |
335 | } |