Add *.exe to gitignore for Cygwin
[urcu.git] / src / urcu-qsbr.c
1 /*
2 * urcu-qsbr.c
3 *
4 * Userspace RCU QSBR library
5 *
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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 #define _LGPL_SOURCE
27 #include <stdio.h>
28 #include <pthread.h>
29 #include <signal.h>
30 #include <assert.h>
31 #include <stdlib.h>
32 #include <stdint.h>
33 #include <string.h>
34 #include <errno.h>
35 #include <poll.h>
36
37 #include "urcu/wfcqueue.h"
38 #include "urcu/map/urcu-qsbr.h"
39 #define BUILD_QSBR_LIB
40 #include "urcu/static/urcu-qsbr.h"
41 #include "urcu-pointer.h"
42 #include "urcu/tls-compat.h"
43
44 #include "urcu-die.h"
45 #include "urcu-wait.h"
46
47 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
48 #undef _LGPL_SOURCE
49 #include "urcu-qsbr.h"
50 #define _LGPL_SOURCE
51
52 void __attribute__((destructor)) rcu_exit(void);
53
54 /*
55 * rcu_gp_lock ensures mutual exclusion between threads calling
56 * synchronize_rcu().
57 */
58 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
59 /*
60 * rcu_registry_lock ensures mutual exclusion between threads
61 * registering and unregistering themselves to/from the registry, and
62 * with threads reading that registry from synchronize_rcu(). However,
63 * this lock is not held all the way through the completion of awaiting
64 * for the grace period. It is sporadically released between iterations
65 * on the registry.
66 * rcu_registry_lock may nest inside rcu_gp_lock.
67 */
68 static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
69 struct rcu_gp rcu_gp = { .ctr = RCU_GP_ONLINE };
70
71 /*
72 * Active attempts to check for reader Q.S. before calling futex().
73 */
74 #define RCU_QS_ACTIVE_ATTEMPTS 100
75
76 /*
77 * Written to only by each individual reader. Read by both the reader and the
78 * writers.
79 */
80 DEFINE_URCU_TLS(struct rcu_reader, rcu_reader);
81
82 static CDS_LIST_HEAD(registry);
83
84 /*
85 * Queue keeping threads awaiting to wait for a grace period. Contains
86 * struct gp_waiters_thread objects.
87 */
88 static DEFINE_URCU_WAIT_QUEUE(gp_waiters);
89
90 static void mutex_lock(pthread_mutex_t *mutex)
91 {
92 int ret;
93
94 #ifndef DISTRUST_SIGNALS_EXTREME
95 ret = pthread_mutex_lock(mutex);
96 if (ret)
97 urcu_die(ret);
98 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
99 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
100 if (ret != EBUSY && ret != EINTR)
101 urcu_die(ret);
102 poll(NULL,0,10);
103 }
104 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
105 }
106
107 static void mutex_unlock(pthread_mutex_t *mutex)
108 {
109 int ret;
110
111 ret = pthread_mutex_unlock(mutex);
112 if (ret)
113 urcu_die(ret);
114 }
115
116 /*
117 * synchronize_rcu() waiting. Single thread.
118 */
119 static void wait_gp(void)
120 {
121 /* Read reader_gp before read futex */
122 cmm_smp_rmb();
123 if (uatomic_read(&rcu_gp.futex) != -1)
124 return;
125 while (futex_noasync(&rcu_gp.futex, FUTEX_WAIT, -1,
126 NULL, NULL, 0)) {
127 switch (errno) {
128 case EWOULDBLOCK:
129 /* Value already changed. */
130 return;
131 case EINTR:
132 /* Retry if interrupted by signal. */
133 break; /* Get out of switch. */
134 default:
135 /* Unexpected error. */
136 urcu_die(errno);
137 }
138 }
139 }
140
141 /*
142 * Always called with rcu_registry lock held. Releases this lock between
143 * iterations and grabs it again. Holds the lock when it returns.
144 */
145 static void wait_for_readers(struct cds_list_head *input_readers,
146 struct cds_list_head *cur_snap_readers,
147 struct cds_list_head *qsreaders)
148 {
149 unsigned int wait_loops = 0;
150 struct rcu_reader *index, *tmp;
151
152 /*
153 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
154 * indicate quiescence (offline), or for them to observe the
155 * current rcu_gp.ctr value.
156 */
157 for (;;) {
158 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
159 wait_loops++;
160 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
161 uatomic_set(&rcu_gp.futex, -1);
162 /*
163 * Write futex before write waiting (the other side
164 * reads them in the opposite order).
165 */
166 cmm_smp_wmb();
167 cds_list_for_each_entry(index, input_readers, node) {
168 _CMM_STORE_SHARED(index->waiting, 1);
169 }
170 /* Write futex before read reader_gp */
171 cmm_smp_mb();
172 }
173 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
174 switch (rcu_reader_state(&index->ctr)) {
175 case RCU_READER_ACTIVE_CURRENT:
176 if (cur_snap_readers) {
177 cds_list_move(&index->node,
178 cur_snap_readers);
179 break;
180 }
181 /* Fall-through */
182 case RCU_READER_INACTIVE:
183 cds_list_move(&index->node, qsreaders);
184 break;
185 case RCU_READER_ACTIVE_OLD:
186 /*
187 * Old snapshot. Leaving node in
188 * input_readers will make us busy-loop
189 * until the snapshot becomes current or
190 * the reader becomes inactive.
191 */
192 break;
193 }
194 }
195
196 if (cds_list_empty(input_readers)) {
197 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
198 /* Read reader_gp before write futex */
199 cmm_smp_mb();
200 uatomic_set(&rcu_gp.futex, 0);
201 }
202 break;
203 } else {
204 /* Temporarily unlock the registry lock. */
205 mutex_unlock(&rcu_registry_lock);
206 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
207 wait_gp();
208 } else {
209 #ifndef HAS_INCOHERENT_CACHES
210 caa_cpu_relax();
211 #else /* #ifndef HAS_INCOHERENT_CACHES */
212 cmm_smp_mb();
213 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
214 }
215 /* Re-lock the registry lock before the next loop. */
216 mutex_lock(&rcu_registry_lock);
217 }
218 }
219 }
220
221 /*
222 * Using a two-subphases algorithm for architectures with smaller than 64-bit
223 * long-size to ensure we do not encounter an overflow bug.
224 */
225
226 #if (CAA_BITS_PER_LONG < 64)
227 void synchronize_rcu(void)
228 {
229 CDS_LIST_HEAD(cur_snap_readers);
230 CDS_LIST_HEAD(qsreaders);
231 unsigned long was_online;
232 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
233 struct urcu_waiters waiters;
234
235 was_online = rcu_read_ongoing();
236
237 /* All threads should read qparity before accessing data structure
238 * where new ptr points to. In the "then" case, rcu_thread_offline
239 * includes a memory barrier.
240 *
241 * Mark the writer thread offline to make sure we don't wait for
242 * our own quiescent state. This allows using synchronize_rcu()
243 * in threads registered as readers.
244 */
245 if (was_online)
246 rcu_thread_offline();
247 else
248 cmm_smp_mb();
249
250 /*
251 * Add ourself to gp_waiters queue of threads awaiting to wait
252 * for a grace period. Proceed to perform the grace period only
253 * if we are the first thread added into the queue.
254 */
255 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
256 /* Not first in queue: will be awakened by another thread. */
257 urcu_adaptative_busy_wait(&wait);
258 goto gp_end;
259 }
260 /* We won't need to wake ourself up */
261 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
262
263 mutex_lock(&rcu_gp_lock);
264
265 /*
266 * Move all waiters into our local queue.
267 */
268 urcu_move_waiters(&waiters, &gp_waiters);
269
270 mutex_lock(&rcu_registry_lock);
271
272 if (cds_list_empty(&registry))
273 goto out;
274
275 /*
276 * Wait for readers to observe original parity or be quiescent.
277 * wait_for_readers() can release and grab again rcu_registry_lock
278 * interally.
279 */
280 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
281
282 /*
283 * Must finish waiting for quiescent state for original parity
284 * before committing next rcu_gp.ctr update to memory. Failure
285 * to do so could result in the writer waiting forever while new
286 * readers are always accessing data (no progress). Enforce
287 * compiler-order of load URCU_TLS(rcu_reader).ctr before store
288 * to rcu_gp.ctr.
289 */
290 cmm_barrier();
291
292 /*
293 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
294 * model easier to understand. It does not have a big performance impact
295 * anyway, given this is the write-side.
296 */
297 cmm_smp_mb();
298
299 /* Switch parity: 0 -> 1, 1 -> 0 */
300 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr ^ RCU_GP_CTR);
301
302 /*
303 * Must commit rcu_gp.ctr update to memory before waiting for
304 * quiescent state. Failure to do so could result in the writer
305 * waiting forever while new readers are always accessing data
306 * (no progress). Enforce compiler-order of store to rcu_gp.ctr
307 * before load URCU_TLS(rcu_reader).ctr.
308 */
309 cmm_barrier();
310
311 /*
312 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
313 * model easier to understand. It does not have a big performance impact
314 * anyway, given this is the write-side.
315 */
316 cmm_smp_mb();
317
318 /*
319 * Wait for readers to observe new parity or be quiescent.
320 * wait_for_readers() can release and grab again rcu_registry_lock
321 * interally.
322 */
323 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
324
325 /*
326 * Put quiescent reader list back into registry.
327 */
328 cds_list_splice(&qsreaders, &registry);
329 out:
330 mutex_unlock(&rcu_registry_lock);
331 mutex_unlock(&rcu_gp_lock);
332 urcu_wake_all_waiters(&waiters);
333 gp_end:
334 /*
335 * Finish waiting for reader threads before letting the old ptr being
336 * freed.
337 */
338 if (was_online)
339 rcu_thread_online();
340 else
341 cmm_smp_mb();
342 }
343 #else /* !(CAA_BITS_PER_LONG < 64) */
344 void synchronize_rcu(void)
345 {
346 CDS_LIST_HEAD(qsreaders);
347 unsigned long was_online;
348 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
349 struct urcu_waiters waiters;
350
351 was_online = rcu_read_ongoing();
352
353 /*
354 * Mark the writer thread offline to make sure we don't wait for
355 * our own quiescent state. This allows using synchronize_rcu()
356 * in threads registered as readers.
357 */
358 if (was_online)
359 rcu_thread_offline();
360 else
361 cmm_smp_mb();
362
363 /*
364 * Add ourself to gp_waiters queue of threads awaiting to wait
365 * for a grace period. Proceed to perform the grace period only
366 * if we are the first thread added into the queue.
367 */
368 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
369 /* Not first in queue: will be awakened by another thread. */
370 urcu_adaptative_busy_wait(&wait);
371 goto gp_end;
372 }
373 /* We won't need to wake ourself up */
374 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
375
376 mutex_lock(&rcu_gp_lock);
377
378 /*
379 * Move all waiters into our local queue.
380 */
381 urcu_move_waiters(&waiters, &gp_waiters);
382
383 mutex_lock(&rcu_registry_lock);
384
385 if (cds_list_empty(&registry))
386 goto out;
387
388 /* Increment current G.P. */
389 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr + RCU_GP_CTR);
390
391 /*
392 * Must commit rcu_gp.ctr update to memory before waiting for
393 * quiescent state. Failure to do so could result in the writer
394 * waiting forever while new readers are always accessing data
395 * (no progress). Enforce compiler-order of store to rcu_gp.ctr
396 * before load URCU_TLS(rcu_reader).ctr.
397 */
398 cmm_barrier();
399
400 /*
401 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
402 * model easier to understand. It does not have a big performance impact
403 * anyway, given this is the write-side.
404 */
405 cmm_smp_mb();
406
407 /*
408 * Wait for readers to observe new count of be quiescent.
409 * wait_for_readers() can release and grab again rcu_registry_lock
410 * interally.
411 */
412 wait_for_readers(&registry, NULL, &qsreaders);
413
414 /*
415 * Put quiescent reader list back into registry.
416 */
417 cds_list_splice(&qsreaders, &registry);
418 out:
419 mutex_unlock(&rcu_registry_lock);
420 mutex_unlock(&rcu_gp_lock);
421 urcu_wake_all_waiters(&waiters);
422 gp_end:
423 if (was_online)
424 rcu_thread_online();
425 else
426 cmm_smp_mb();
427 }
428 #endif /* !(CAA_BITS_PER_LONG < 64) */
429
430 /*
431 * library wrappers to be used by non-LGPL compatible source code.
432 */
433
434 void rcu_read_lock(void)
435 {
436 _rcu_read_lock();
437 }
438
439 void rcu_read_unlock(void)
440 {
441 _rcu_read_unlock();
442 }
443
444 int rcu_read_ongoing(void)
445 {
446 return _rcu_read_ongoing();
447 }
448
449 void rcu_quiescent_state(void)
450 {
451 _rcu_quiescent_state();
452 }
453
454 void rcu_thread_offline(void)
455 {
456 _rcu_thread_offline();
457 }
458
459 void rcu_thread_online(void)
460 {
461 _rcu_thread_online();
462 }
463
464 void rcu_register_thread(void)
465 {
466 URCU_TLS(rcu_reader).tid = pthread_self();
467 assert(URCU_TLS(rcu_reader).ctr == 0);
468
469 mutex_lock(&rcu_registry_lock);
470 assert(!URCU_TLS(rcu_reader).registered);
471 URCU_TLS(rcu_reader).registered = 1;
472 cds_list_add(&URCU_TLS(rcu_reader).node, &registry);
473 mutex_unlock(&rcu_registry_lock);
474 _rcu_thread_online();
475 }
476
477 void rcu_unregister_thread(void)
478 {
479 /*
480 * We have to make the thread offline otherwise we end up dealocking
481 * with a waiting writer.
482 */
483 _rcu_thread_offline();
484 assert(URCU_TLS(rcu_reader).registered);
485 URCU_TLS(rcu_reader).registered = 0;
486 mutex_lock(&rcu_registry_lock);
487 cds_list_del(&URCU_TLS(rcu_reader).node);
488 mutex_unlock(&rcu_registry_lock);
489 }
490
491 void rcu_exit(void)
492 {
493 /*
494 * Assertion disabled because call_rcu threads are now rcu
495 * readers, and left running at exit.
496 * assert(cds_list_empty(&registry));
497 */
498 }
499
500 DEFINE_RCU_FLAVOR(rcu_flavor);
501
502 #include "urcu-call-rcu-impl.h"
503 #include "urcu-defer-impl.h"
This page took 0.039214 seconds and 4 git commands to generate.