Add report at the end of configure
[urcu.git] / src / urcu-qsbr.c
CommitLineData
9f1621ca 1/*
7ac06cef 2 * urcu-qsbr.c
9f1621ca 3 *
7ac06cef 4 * Userspace RCU QSBR library
9f1621ca 5 *
6982d6d7 6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
9f1621ca
MD
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
71c811bf 26#define _LGPL_SOURCE
9f1621ca
MD
27#include <stdio.h>
28#include <pthread.h>
29#include <signal.h>
30#include <assert.h>
31#include <stdlib.h>
6d841bc2 32#include <stdint.h>
9f1621ca
MD
33#include <string.h>
34#include <errno.h>
35#include <poll.h>
36
d73fb81f 37#include "urcu/wfcqueue.h"
57760d44 38#include "urcu/map/urcu-qsbr.h"
727f819d 39#define BUILD_QSBR_LIB
af7c2dbe 40#include "urcu/static/urcu-qsbr.h"
618b2595 41#include "urcu-pointer.h"
bd252a04 42#include "urcu/tls-compat.h"
71c811bf 43
4a6d7378 44#include "urcu-die.h"
cba82d7b 45#include "urcu-wait.h"
4a6d7378 46
9f1621ca 47/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
71c811bf 48#undef _LGPL_SOURCE
7ac06cef 49#include "urcu-qsbr.h"
71c811bf 50#define _LGPL_SOURCE
9f1621ca 51
f6d18c64
MD
52void __attribute__((destructor)) rcu_exit(void);
53
731ccb96
MD
54/*
55 * rcu_gp_lock ensures mutual exclusion between threads calling
56 * synchronize_rcu().
57 */
6abb4bd5 58static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
731ccb96
MD
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 */
68static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
4de0cd31 69struct rcu_gp rcu_gp = { .ctr = RCU_GP_ONLINE };
9f1621ca 70
408f6d92
PB
71/*
72 * Active attempts to check for reader Q.S. before calling futex().
73 */
74#define RCU_QS_ACTIVE_ATTEMPTS 100
75
9f1621ca
MD
76/*
77 * Written to only by each individual reader. Read by both the reader and the
78 * writers.
79 */
bd252a04 80DEFINE_URCU_TLS(struct rcu_reader, rcu_reader);
9f1621ca 81
16aa9ee8 82static CDS_LIST_HEAD(registry);
9f1621ca 83
6362f68f 84/*
bf6822a6 85 * Queue keeping threads awaiting to wait for a grace period. Contains
6362f68f
MD
86 * struct gp_waiters_thread objects.
87 */
bf6822a6 88static DEFINE_URCU_WAIT_QUEUE(gp_waiters);
6362f68f 89
6abb4bd5 90static void mutex_lock(pthread_mutex_t *mutex)
9f1621ca
MD
91{
92 int ret;
93
94#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 95 ret = pthread_mutex_lock(mutex);
4a6d7378
MD
96 if (ret)
97 urcu_die(ret);
9f1621ca 98#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 99 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
4a6d7378
MD
100 if (ret != EBUSY && ret != EINTR)
101 urcu_die(ret);
9f1621ca
MD
102 poll(NULL,0,10);
103 }
104#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
105}
106
6abb4bd5 107static void mutex_unlock(pthread_mutex_t *mutex)
9f1621ca
MD
108{
109 int ret;
110
6abb4bd5 111 ret = pthread_mutex_unlock(mutex);
4a6d7378
MD
112 if (ret)
113 urcu_die(ret);
9f1621ca
MD
114}
115
bc6c15bb
MD
116/*
117 * synchronize_rcu() waiting. Single thread.
118 */
4d703340 119static void wait_gp(void)
bc6c15bb 120{
4d703340 121 /* Read reader_gp before read futex */
5481ddb3 122 cmm_smp_rmb();
b0a841b4
MD
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 }
bc6c15bb
MD
139}
140
731ccb96
MD
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 */
708d89f0
MD
145static void wait_for_readers(struct cds_list_head *input_readers,
146 struct cds_list_head *cur_snap_readers,
147 struct cds_list_head *qsreaders)
9f1621ca 148{
9340c38d 149 unsigned int wait_loops = 0;
02be5561 150 struct rcu_reader *index, *tmp;
9f1621ca 151
9f1621ca 152 /*
f6b42f9c
MD
153 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
154 * indicate quiescence (offline), or for them to observe the
15302e28 155 * current rcu_gp.ctr value.
9f1621ca 156 */
4d703340 157 for (;;) {
5e81fed7
MD
158 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
159 wait_loops++;
83a2c421 160 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
15302e28 161 uatomic_set(&rcu_gp.futex, -1);
83a2c421
PB
162 /*
163 * Write futex before write waiting (the other side
164 * reads them in the opposite order).
165 */
166 cmm_smp_wmb();
708d89f0 167 cds_list_for_each_entry(index, input_readers, node) {
83a2c421
PB
168 _CMM_STORE_SHARED(index->waiting, 1);
169 }
4d703340 170 /* Write futex before read reader_gp */
5481ddb3 171 cmm_smp_mb();
4d703340 172 }
708d89f0
MD
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 }
4d703340 194 }
bc6c15bb 195
708d89f0 196 if (cds_list_empty(input_readers)) {
83a2c421 197 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 198 /* Read reader_gp before write futex */
5481ddb3 199 cmm_smp_mb();
15302e28 200 uatomic_set(&rcu_gp.futex, 0);
4d703340
MD
201 }
202 break;
203 } else {
731ccb96
MD
204 /* Temporarily unlock the registry lock. */
205 mutex_unlock(&rcu_registry_lock);
83a2c421 206 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
4d703340 207 wait_gp();
bc6c15bb 208 } else {
9f1621ca 209#ifndef HAS_INCOHERENT_CACHES
06f22bdb 210 caa_cpu_relax();
9f1621ca 211#else /* #ifndef HAS_INCOHERENT_CACHES */
5481ddb3 212 cmm_smp_mb();
9f1621ca 213#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
bc6c15bb 214 }
731ccb96
MD
215 /* Re-lock the registry lock before the next loop. */
216 mutex_lock(&rcu_registry_lock);
bc6c15bb 217 }
9f1621ca
MD
218 }
219}
220
47d2f29e
MD
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
b39e1761 226#if (CAA_BITS_PER_LONG < 64)
47d2f29e
MD
227void synchronize_rcu(void)
228{
708d89f0
MD
229 CDS_LIST_HEAD(cur_snap_readers);
230 CDS_LIST_HEAD(qsreaders);
bc49c323 231 unsigned long was_online;
bf6822a6
MD
232 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
233 struct urcu_waiters waiters;
bc49c323 234
882f3357 235 was_online = rcu_read_ongoing();
bc49c323 236
47d2f29e 237 /* All threads should read qparity before accessing data structure
27b940e7
PB
238 * where new ptr points to. In the "then" case, rcu_thread_offline
239 * includes a memory barrier.
240 *
bc49c323 241 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
242 * our own quiescent state. This allows using synchronize_rcu()
243 * in threads registered as readers.
bc49c323 244 */
27b940e7
PB
245 if (was_online)
246 rcu_thread_offline();
247 else
248 cmm_smp_mb();
bc49c323 249
6362f68f 250 /*
bf6822a6 251 * Add ourself to gp_waiters queue of threads awaiting to wait
6362f68f 252 * for a grace period. Proceed to perform the grace period only
bf6822a6 253 * if we are the first thread added into the queue.
6362f68f 254 */
bf6822a6
MD
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);
6362f68f
MD
258 goto gp_end;
259 }
bf6822a6
MD
260 /* We won't need to wake ourself up */
261 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
6362f68f 262
6abb4bd5 263 mutex_lock(&rcu_gp_lock);
47d2f29e 264
6362f68f 265 /*
bf6822a6 266 * Move all waiters into our local queue.
6362f68f 267 */
bf6822a6 268 urcu_move_waiters(&waiters, &gp_waiters);
6362f68f 269
731ccb96
MD
270 mutex_lock(&rcu_registry_lock);
271
16aa9ee8 272 if (cds_list_empty(&registry))
2dfb8b5e 273 goto out;
47d2f29e
MD
274
275 /*
f6b42f9c 276 * Wait for readers to observe original parity or be quiescent.
731ccb96
MD
277 * wait_for_readers() can release and grab again rcu_registry_lock
278 * interally.
47d2f29e 279 */
708d89f0 280 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
47d2f29e
MD
281
282 /*
f6b42f9c 283 * Must finish waiting for quiescent state for original parity
15302e28 284 * before committing next rcu_gp.ctr update to memory. Failure
f6b42f9c 285 * to do so could result in the writer waiting forever while new
5e77fc1f 286 * readers are always accessing data (no progress). Enforce
f6b42f9c 287 * compiler-order of load URCU_TLS(rcu_reader).ctr before store
15302e28 288 * to rcu_gp.ctr.
47d2f29e 289 */
5481ddb3 290 cmm_barrier();
47d2f29e 291
47d2f29e 292 /*
5481ddb3 293 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
2dfb8b5e
MD
294 * model easier to understand. It does not have a big performance impact
295 * anyway, given this is the write-side.
47d2f29e 296 */
5481ddb3 297 cmm_smp_mb();
47d2f29e 298
f6b42f9c 299 /* Switch parity: 0 -> 1, 1 -> 0 */
15302e28 300 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr ^ RCU_GP_CTR);
f6b42f9c 301
47d2f29e 302 /*
15302e28 303 * Must commit rcu_gp.ctr update to memory before waiting for
f6b42f9c
MD
304 * quiescent state. Failure to do so could result in the writer
305 * waiting forever while new readers are always accessing data
15302e28 306 * (no progress). Enforce compiler-order of store to rcu_gp.ctr
f6b42f9c 307 * before load URCU_TLS(rcu_reader).ctr.
47d2f29e 308 */
f6b42f9c
MD
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.
731ccb96
MD
320 * wait_for_readers() can release and grab again rcu_registry_lock
321 * interally.
f6b42f9c 322 */
708d89f0
MD
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);
2dfb8b5e 329out:
731ccb96 330 mutex_unlock(&rcu_registry_lock);
6abb4bd5 331 mutex_unlock(&rcu_gp_lock);
bf6822a6 332 urcu_wake_all_waiters(&waiters);
6362f68f 333gp_end:
bc49c323
MD
334 /*
335 * Finish waiting for reader threads before letting the old ptr being
47d2f29e
MD
336 * freed.
337 */
bc49c323 338 if (was_online)
27b940e7
PB
339 rcu_thread_online();
340 else
341 cmm_smp_mb();
47d2f29e 342}
b39e1761 343#else /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
344void synchronize_rcu(void)
345{
708d89f0 346 CDS_LIST_HEAD(qsreaders);
f0f7dbdd 347 unsigned long was_online;
bf6822a6
MD
348 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
349 struct urcu_waiters waiters;
ff2f67a0 350
882f3357 351 was_online = rcu_read_ongoing();
ff2f67a0
MD
352
353 /*
354 * Mark the writer thread offline to make sure we don't wait for
5e77fc1f
PM
355 * our own quiescent state. This allows using synchronize_rcu()
356 * in threads registered as readers.
ff2f67a0 357 */
27b940e7
PB
358 if (was_online)
359 rcu_thread_offline();
360 else
361 cmm_smp_mb();
ff2f67a0 362
6362f68f 363 /*
bf6822a6 364 * Add ourself to gp_waiters queue of threads awaiting to wait
6362f68f 365 * for a grace period. Proceed to perform the grace period only
bf6822a6 366 * if we are the first thread added into the queue.
6362f68f 367 */
bf6822a6
MD
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);
6362f68f
MD
371 goto gp_end;
372 }
bf6822a6
MD
373 /* We won't need to wake ourself up */
374 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
6362f68f 375
6abb4bd5 376 mutex_lock(&rcu_gp_lock);
6362f68f
MD
377
378 /*
bf6822a6 379 * Move all waiters into our local queue.
6362f68f 380 */
bf6822a6 381 urcu_move_waiters(&waiters, &gp_waiters);
6362f68f 382
731ccb96
MD
383 mutex_lock(&rcu_registry_lock);
384
16aa9ee8 385 if (cds_list_empty(&registry))
2dfb8b5e 386 goto out;
f6b42f9c
MD
387
388 /* Increment current G.P. */
15302e28 389 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr + RCU_GP_CTR);
f6b42f9c
MD
390
391 /*
15302e28 392 * Must commit rcu_gp.ctr update to memory before waiting for
f6b42f9c
MD
393 * quiescent state. Failure to do so could result in the writer
394 * waiting forever while new readers are always accessing data
15302e28 395 * (no progress). Enforce compiler-order of store to rcu_gp.ctr
f6b42f9c
MD
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.
731ccb96
MD
409 * wait_for_readers() can release and grab again rcu_registry_lock
410 * interally.
f6b42f9c 411 */
708d89f0
MD
412 wait_for_readers(&registry, NULL, &qsreaders);
413
414 /*
415 * Put quiescent reader list back into registry.
416 */
417 cds_list_splice(&qsreaders, &registry);
2dfb8b5e 418out:
731ccb96 419 mutex_unlock(&rcu_registry_lock);
6abb4bd5 420 mutex_unlock(&rcu_gp_lock);
bf6822a6 421 urcu_wake_all_waiters(&waiters);
6362f68f 422gp_end:
ff2f67a0 423 if (was_online)
27b940e7
PB
424 rcu_thread_online();
425 else
426 cmm_smp_mb();
9f1621ca 427}
b39e1761 428#endif /* !(CAA_BITS_PER_LONG < 64) */
9f1621ca
MD
429
430/*
431 * library wrappers to be used by non-LGPL compatible source code.
432 */
433
434void rcu_read_lock(void)
435{
436 _rcu_read_lock();
437}
438
439void rcu_read_unlock(void)
440{
441 _rcu_read_unlock();
442}
443
882f3357
MD
444int rcu_read_ongoing(void)
445{
446 return _rcu_read_ongoing();
447}
448
7ac06cef
MD
449void rcu_quiescent_state(void)
450{
451 _rcu_quiescent_state();
452}
453
454void rcu_thread_offline(void)
455{
456 _rcu_thread_offline();
457}
458
459void rcu_thread_online(void)
460{
461 _rcu_thread_online();
462}
463
9f1621ca
MD
464void rcu_register_thread(void)
465{
bd252a04
MD
466 URCU_TLS(rcu_reader).tid = pthread_self();
467 assert(URCU_TLS(rcu_reader).ctr == 0);
4f8e3380 468
731ccb96 469 mutex_lock(&rcu_registry_lock);
a77f7d82
MD
470 assert(!URCU_TLS(rcu_reader).registered);
471 URCU_TLS(rcu_reader).registered = 1;
bd252a04 472 cds_list_add(&URCU_TLS(rcu_reader).node, &registry);
731ccb96 473 mutex_unlock(&rcu_registry_lock);
5f373c84 474 _rcu_thread_online();
9f1621ca
MD
475}
476
477void rcu_unregister_thread(void)
478{
76f3022f
MD
479 /*
480 * We have to make the thread offline otherwise we end up dealocking
481 * with a waiting writer.
482 */
483 _rcu_thread_offline();
a77f7d82
MD
484 assert(URCU_TLS(rcu_reader).registered);
485 URCU_TLS(rcu_reader).registered = 0;
731ccb96 486 mutex_lock(&rcu_registry_lock);
bd252a04 487 cds_list_del(&URCU_TLS(rcu_reader).node);
731ccb96 488 mutex_unlock(&rcu_registry_lock);
9f1621ca 489}
f6d18c64
MD
490
491void rcu_exit(void)
492{
01cadde4
MD
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 */
f6d18c64 498}
5e77fc1f 499
5e6b23a6 500DEFINE_RCU_FLAVOR(rcu_flavor);
541d828d 501
5e77fc1f 502#include "urcu-call-rcu-impl.h"
0376e7b2 503#include "urcu-defer-impl.h"
This page took 0.065287 seconds and 4 git commands to generate.