doc/examples: Remove urcu-signal example
[urcu.git] / src / urcu.c
CommitLineData
acdb82a2
MJ
1// SPDX-FileCopyrightText: 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2// SPDX-FileCopyrightText: 2009 Paul E. McKenney, IBM Corporation.
3//
4// SPDX-License-Identifier: LGPL-2.1-or-later
5
b257a10b 6/*
b257a10b
MD
7 * Userspace RCU library
8 *
54843abc 9 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
b257a10b
MD
10 */
11
e37faee1 12#define URCU_NO_COMPAT_IDENTIFIERS
fdf01eed 13#define _BSD_SOURCE
71c811bf 14#define _LGPL_SOURCE
82d50e1a 15#define _DEFAULT_SOURCE
27b012e2
MD
16#include <stdio.h>
17#include <pthread.h>
18#include <signal.h>
f69f195a 19#include <stdlib.h>
6d841bc2 20#include <stdint.h>
f69f195a 21#include <string.h>
09a9f986 22#include <errno.h>
c0bb9f69 23#include <stdbool.h>
e8043c1b 24#include <poll.h>
27b012e2 25
375db287 26#include <urcu/config.h>
601922a8 27#include <urcu/annotate.h>
01477510 28#include <urcu/assert.h>
4477a870
MD
29#include <urcu/arch.h>
30#include <urcu/wfcqueue.h>
31#include <urcu/map/urcu.h>
32#include <urcu/static/urcu.h>
33#include <urcu/pointer.h>
34#include <urcu/tls-compat.h>
71c811bf 35
4a6d7378 36#include "urcu-die.h"
5bffdd5d 37#include "urcu-wait.h"
4477a870 38#include "urcu-utils.h"
4a6d7378 39
4477a870 40#define URCU_API_MAP
121a5d44 41/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
71c811bf 42#undef _LGPL_SOURCE
4477a870 43#include <urcu/urcu.h>
71c811bf 44#define _LGPL_SOURCE
27b012e2 45
3a71751e
PB
46/*
47 * If a reader is really non-cooperative and refuses to commit its
48 * rcu_active_readers count to memory (there is no barrier in the reader
9340c38d 49 * per-se), kick it after 10 loops waiting for it.
3a71751e 50 */
9340c38d 51#define KICK_READER_LOOPS 10
3a71751e
PB
52
53/*
54 * Active attempts to check for reader Q.S. before calling futex().
55 */
56#define RCU_QS_ACTIVE_ATTEMPTS 100
57
999991c6
MD
58/* If the headers do not support membarrier system call, fall back on RCU_MB */
59#ifdef __NR_membarrier
60# define membarrier(...) syscall(__NR_membarrier, __VA_ARGS__)
553b7eb9
MD
61#else
62# define membarrier(...) -ENOSYS
63#endif
64
64f469e6 65enum membarrier_cmd {
c0bb9f69
MD
66 MEMBARRIER_CMD_QUERY = 0,
67 MEMBARRIER_CMD_SHARED = (1 << 0),
68 /* reserved for MEMBARRIER_CMD_SHARED_EXPEDITED (1 << 1) */
69 /* reserved for MEMBARRIER_CMD_PRIVATE (1 << 2) */
70 MEMBARRIER_CMD_PRIVATE_EXPEDITED = (1 << 3),
71 MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED = (1 << 4),
64f469e6 72};
553b7eb9 73
fdf01eed 74#ifdef RCU_MEMBARRIER
834a45ba 75static int init_done;
4477a870 76static int urcu_memb_has_sys_membarrier_private_expedited;
c0bb9f69 77
d8d9a340 78#ifndef CONFIG_RCU_FORCE_SYS_MEMBARRIER
4477a870
MD
79/*
80 * Explicitly initialize to zero because we can't alias a non-static
81 * uninitialized variable.
82 */
83int urcu_memb_has_sys_membarrier = 0;
d8d9a340 84#endif
834a45ba 85
02be5561 86void __attribute__((constructor)) rcu_init(void);
fdf01eed
MD
87#endif
88
97d13221 89#if defined(RCU_MB) || defined(RCU_SIGNAL)
02be5561 90void rcu_init(void)
e90a6e9c
MD
91{
92}
93#endif
8a5fb4c9 94
90f72b8c
MD
95void __attribute__((destructor)) rcu_exit(void);
96static void urcu_call_rcu_exit(void);
97
731ccb96
MD
98/*
99 * rcu_gp_lock ensures mutual exclusion between threads calling
100 * synchronize_rcu().
101 */
6abb4bd5 102static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
731ccb96
MD
103/*
104 * rcu_registry_lock ensures mutual exclusion between threads
105 * registering and unregistering themselves to/from the registry, and
106 * with threads reading that registry from synchronize_rcu(). However,
107 * this lock is not held all the way through the completion of awaiting
108 * for the grace period. It is sporadically released between iterations
109 * on the registry.
110 * rcu_registry_lock may nest inside rcu_gp_lock.
111 */
112static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
4477a870 113struct urcu_gp rcu_gp = { .ctr = URCU_GP_COUNT };
27b012e2 114
b0d5e790
MD
115/*
116 * Written to only by each individual reader. Read by both the reader and the
117 * writers.
118 */
4477a870 119DEFINE_URCU_TLS(struct urcu_reader, rcu_reader);
27b012e2 120
16aa9ee8 121static CDS_LIST_HEAD(registry);
27b012e2 122
5bffdd5d
MD
123/*
124 * Queue keeping threads awaiting to wait for a grace period. Contains
125 * struct gp_waiters_thread objects.
126 */
127static DEFINE_URCU_WAIT_QUEUE(gp_waiters);
128
6abb4bd5 129static void mutex_lock(pthread_mutex_t *mutex)
41718ff9
MD
130{
131 int ret;
09a9f986
PM
132
133#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 134 ret = pthread_mutex_lock(mutex);
4a6d7378
MD
135 if (ret)
136 urcu_die(ret);
09a9f986 137#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 138 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
4a6d7378
MD
139 if (ret != EBUSY && ret != EINTR)
140 urcu_die(ret);
bd252a04 141 if (CMM_LOAD_SHARED(URCU_TLS(rcu_reader).need_mb)) {
5481ddb3 142 cmm_smp_mb();
bd252a04 143 _CMM_STORE_SHARED(URCU_TLS(rcu_reader).need_mb, 0);
5481ddb3 144 cmm_smp_mb();
09a9f986 145 }
8999a9ee 146 (void) poll(NULL, 0, 10);
09a9f986
PM
147 }
148#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
41718ff9
MD
149}
150
6abb4bd5 151static void mutex_unlock(pthread_mutex_t *mutex)
41718ff9
MD
152{
153 int ret;
154
6abb4bd5 155 ret = pthread_mutex_unlock(mutex);
4a6d7378
MD
156 if (ret)
157 urcu_die(ret);
41718ff9
MD
158}
159
fdf01eed 160#ifdef RCU_MEMBARRIER
a4922ed9 161static void smp_mb_master(void)
fdf01eed 162{
4477a870
MD
163 if (caa_likely(urcu_memb_has_sys_membarrier)) {
164 if (membarrier(urcu_memb_has_sys_membarrier_private_expedited ?
c0bb9f69
MD
165 MEMBARRIER_CMD_PRIVATE_EXPEDITED :
166 MEMBARRIER_CMD_SHARED, 0))
167 urcu_die(errno);
168 } else {
5481ddb3 169 cmm_smp_mb();
c0bb9f69 170 }
fdf01eed
MD
171}
172#endif
173
97d13221 174#if defined(RCU_MB) || defined(RCU_SIGNAL)
a4922ed9 175static void smp_mb_master(void)
40e140c9 176{
5481ddb3 177 cmm_smp_mb();
40e140c9 178}
fdf01eed
MD
179#endif
180
bc6c15bb
MD
181/*
182 * synchronize_rcu() waiting. Single thread.
fca9fb96
MD
183 * Always called with rcu_registry lock held. Releases this lock and
184 * grabs it again. Holds the lock when it returns.
bc6c15bb 185 */
cfe78e25 186static void wait_gp(void)
bc6c15bb 187{
fca9fb96 188 /*
97d13221 189 * Read reader_gp before read futex.
fca9fb96 190 */
a4922ed9 191 smp_mb_master();
fca9fb96
MD
192 /* Temporarily unlock the registry lock. */
193 mutex_unlock(&rcu_registry_lock);
a18d0428
MD
194 while (uatomic_read(&rcu_gp.futex) == -1) {
195 if (!futex_async(&rcu_gp.futex, FUTEX_WAIT, -1, NULL, NULL, 0)) {
196 /*
197 * Prior queued wakeups queued by unrelated code
198 * using the same address can cause futex wait to
199 * return 0 even through the futex value is still
200 * -1 (spurious wakeups). Check the value again
201 * in user-space to validate whether it really
202 * differs from -1.
203 */
204 continue;
205 }
b0a841b4 206 switch (errno) {
a18d0428 207 case EAGAIN:
b0a841b4 208 /* Value already changed. */
fca9fb96 209 goto end;
b0a841b4
MD
210 case EINTR:
211 /* Retry if interrupted by signal. */
a18d0428 212 break; /* Get out of switch. Check again. */
b0a841b4
MD
213 default:
214 /* Unexpected error. */
215 urcu_die(errno);
216 }
217 }
fca9fb96
MD
218end:
219 /*
220 * Re-lock the registry lock before the next loop.
221 */
222 mutex_lock(&rcu_registry_lock);
bc6c15bb
MD
223}
224
731ccb96
MD
225/*
226 * Always called with rcu_registry lock held. Releases this lock between
227 * iterations and grabs it again. Holds the lock when it returns.
228 */
fd189fa5
MD
229static void wait_for_readers(struct cds_list_head *input_readers,
230 struct cds_list_head *cur_snap_readers,
601922a8
OD
231 struct cds_list_head *qsreaders,
232 cmm_annotate_t *group)
27b012e2 233{
9340c38d 234 unsigned int wait_loops = 0;
4477a870 235 struct urcu_reader *index, *tmp;
9340c38d
MD
236#ifdef HAS_INCOHERENT_CACHES
237 unsigned int wait_gp_loops = 0;
238#endif /* HAS_INCOHERENT_CACHES */
27b012e2 239
40e140c9 240 /*
c9488684
MD
241 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
242 * indicate quiescence (not nested), or observe the current
ed1b099e 243 * rcu_gp.ctr value.
27b012e2 244 */
cfe78e25 245 for (;;) {
5e81fed7
MD
246 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
247 wait_loops++;
9340c38d 248 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
ed1b099e 249 uatomic_dec(&rcu_gp.futex);
cfe78e25 250 /* Write futex before read reader_gp */
a4922ed9 251 smp_mb_master();
cfe78e25
MD
252 }
253
fd189fa5 254 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
601922a8 255 switch (urcu_common_reader_state(&rcu_gp, &index->ctr, group)) {
4477a870 256 case URCU_READER_ACTIVE_CURRENT:
fd189fa5
MD
257 if (cur_snap_readers) {
258 cds_list_move(&index->node,
259 cur_snap_readers);
260 break;
261 }
262 /* Fall-through */
4477a870 263 case URCU_READER_INACTIVE:
fd189fa5
MD
264 cds_list_move(&index->node, qsreaders);
265 break;
4477a870 266 case URCU_READER_ACTIVE_OLD:
fd189fa5
MD
267 /*
268 * Old snapshot. Leaving node in
269 * input_readers will make us busy-loop
270 * until the snapshot becomes current or
271 * the reader becomes inactive.
272 */
273 break;
274 }
cfe78e25
MD
275 }
276
e8043c1b 277#ifndef HAS_INCOHERENT_CACHES
fd189fa5 278 if (cds_list_empty(input_readers)) {
9340c38d 279 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
cfe78e25 280 /* Read reader_gp before write futex */
a4922ed9 281 smp_mb_master();
ed1b099e 282 uatomic_set(&rcu_gp.futex, 0);
bc6c15bb 283 }
cfe78e25
MD
284 break;
285 } else {
fca9fb96
MD
286 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
287 /* wait_gp unlocks/locks registry lock. */
cfe78e25 288 wait_gp();
fca9fb96
MD
289 } else {
290 /* Temporarily unlock the registry lock. */
291 mutex_unlock(&rcu_registry_lock);
06f22bdb 292 caa_cpu_relax();
fca9fb96
MD
293 /*
294 * Re-lock the registry lock before the
295 * next loop.
296 */
297 mutex_lock(&rcu_registry_lock);
298 }
bc6c15bb 299 }
e8043c1b 300#else /* #ifndef HAS_INCOHERENT_CACHES */
27b012e2 301 /*
40e140c9 302 * BUSY-LOOP. Force the reader thread to commit its
bd252a04
MD
303 * URCU_TLS(rcu_reader).ctr update to memory if we wait
304 * for too long.
27b012e2 305 */
fd189fa5 306 if (cds_list_empty(input_readers)) {
9340c38d 307 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
cfe78e25 308 /* Read reader_gp before write futex */
a4922ed9 309 smp_mb_master();
ed1b099e 310 uatomic_set(&rcu_gp.futex, 0);
cfe78e25
MD
311 }
312 break;
313 } else {
9340c38d 314 if (wait_gp_loops == KICK_READER_LOOPS) {
a4922ed9 315 smp_mb_master();
9340c38d
MD
316 wait_gp_loops = 0;
317 }
318 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
fca9fb96 319 /* wait_gp unlocks/locks registry lock. */
9340c38d
MD
320 wait_gp();
321 wait_gp_loops++;
322 } else {
fca9fb96
MD
323 /* Temporarily unlock the registry lock. */
324 mutex_unlock(&rcu_registry_lock);
06f22bdb 325 caa_cpu_relax();
fca9fb96
MD
326 /*
327 * Re-lock the registry lock before the
328 * next loop.
329 */
330 mutex_lock(&rcu_registry_lock);
40e140c9
MD
331 }
332 }
e8043c1b 333#endif /* #else #ifndef HAS_INCOHERENT_CACHES */
27b012e2 334 }
27b012e2
MD
335}
336
9598a481 337void synchronize_rcu(void)
2bc59bd7 338{
601922a8
OD
339 cmm_annotate_define(acquire_group);
340 cmm_annotate_define(release_group);
fd189fa5
MD
341 CDS_LIST_HEAD(cur_snap_readers);
342 CDS_LIST_HEAD(qsreaders);
5bffdd5d
MD
343 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
344 struct urcu_waiters waiters;
345
346 /*
347 * Add ourself to gp_waiters queue of threads awaiting to wait
348 * for a grace period. Proceed to perform the grace period only
349 * if we are the first thread added into the queue.
350 * The implicit memory barrier before urcu_wait_add()
351 * orders prior memory accesses of threads put into the wait
352 * queue before their insertion into the wait queue.
353 */
354 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
601922a8
OD
355 /*
356 * Not first in queue: will be awakened by another thread.
357 * Implies a memory barrier after grace period.
358 */
5bffdd5d 359 urcu_adaptative_busy_wait(&wait);
5bffdd5d
MD
360 return;
361 }
362 /* We won't need to wake ourself up */
363 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
fd189fa5 364
6abb4bd5 365 mutex_lock(&rcu_gp_lock);
135530fd 366
5bffdd5d
MD
367 /*
368 * Move all waiters into our local queue.
369 */
370 urcu_move_waiters(&waiters, &gp_waiters);
371
731ccb96
MD
372 mutex_lock(&rcu_registry_lock);
373
16aa9ee8 374 if (cds_list_empty(&registry))
2dfb8b5e
MD
375 goto out;
376
731ccb96
MD
377 /*
378 * All threads should read qparity before accessing data structure
379 * where new ptr points to. Must be done within rcu_registry_lock
380 * because it iterates on reader threads.
381 */
9598a481 382 /* Write new ptr before changing the qparity */
a4922ed9 383 smp_mb_master();
601922a8 384 cmm_annotate_group_mb_release(&release_group);
9598a481 385
9598a481 386 /*
c9488684 387 * Wait for readers to observe original parity or be quiescent.
731ccb96 388 * wait_for_readers() can release and grab again rcu_registry_lock
f99c6e92 389 * internally.
9598a481 390 */
601922a8 391 wait_for_readers(&registry, &cur_snap_readers, &qsreaders, &acquire_group);
9598a481
MD
392
393 /*
c9488684 394 * Must finish waiting for quiescent state for original parity before
ed1b099e 395 * committing next rcu_gp.ctr update to memory. Failure to do so could
d40fde2c
MD
396 * result in the writer waiting forever while new readers are always
397 * accessing data (no progress). Enforce compiler-order of load
ed1b099e 398 * URCU_TLS(rcu_reader).ctr before store to rcu_gp.ctr.
9598a481 399 */
5481ddb3 400 cmm_barrier();
9598a481 401
5dba80f9 402 /*
5481ddb3 403 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
5dba80f9
MD
404 * model easier to understand. It does not have a big performance impact
405 * anyway, given this is the write-side.
406 */
5481ddb3 407 cmm_smp_mb();
67c2d80b 408
c9488684 409 /* Switch parity: 0 -> 1, 1 -> 0 */
601922a8
OD
410 cmm_annotate_group_mem_release(&release_group, &rcu_gp.ctr);
411 uatomic_store(&rcu_gp.ctr, rcu_gp.ctr ^ URCU_GP_CTR_PHASE, CMM_RELAXED);
c9488684
MD
412
413 /*
ed1b099e 414 * Must commit rcu_gp.ctr update to memory before waiting for quiescent
c9488684
MD
415 * state. Failure to do so could result in the writer waiting forever
416 * while new readers are always accessing data (no progress). Enforce
ed1b099e 417 * compiler-order of store to rcu_gp.ctr before load rcu_reader ctr.
c9488684
MD
418 */
419 cmm_barrier();
420
421 /*
422 *
423 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
424 * model easier to understand. It does not have a big performance impact
425 * anyway, given this is the write-side.
426 */
427 cmm_smp_mb();
428
9598a481 429 /*
c9488684 430 * Wait for readers to observe new parity or be quiescent.
731ccb96 431 * wait_for_readers() can release and grab again rcu_registry_lock
f99c6e92 432 * internally.
9598a481 433 */
601922a8 434 wait_for_readers(&cur_snap_readers, NULL, &qsreaders, &acquire_group);
fd189fa5
MD
435
436 /*
437 * Put quiescent reader list back into registry.
438 */
439 cds_list_splice(&qsreaders, &registry);
9598a481 440
731ccb96
MD
441 /*
442 * Finish waiting for reader threads before letting the old ptr
443 * being freed. Must be done within rcu_registry_lock because it
444 * iterates on reader threads.
445 */
a4922ed9 446 smp_mb_master();
601922a8 447 cmm_annotate_group_mb_acquire(&acquire_group);
2dfb8b5e 448out:
731ccb96 449 mutex_unlock(&rcu_registry_lock);
6abb4bd5 450 mutex_unlock(&rcu_gp_lock);
5bffdd5d
MD
451
452 /*
453 * Wakeup waiters only after we have completed the grace period
454 * and have ensured the memory barriers at the end of the grace
455 * period have been issued.
456 */
457 urcu_wake_all_waiters(&waiters);
2bc59bd7
PM
458}
459
121a5d44
MD
460/*
461 * library wrappers to be used by non-LGPL compatible source code.
462 */
463
464void rcu_read_lock(void)
465{
466 _rcu_read_lock();
467}
468
469void rcu_read_unlock(void)
470{
471 _rcu_read_unlock();
472}
473
882f3357
MD
474int rcu_read_ongoing(void)
475{
476 return _rcu_read_ongoing();
477}
478
121a5d44 479void rcu_register_thread(void)
27b012e2 480{
bd252a04 481 URCU_TLS(rcu_reader).tid = pthread_self();
01477510
FD
482 urcu_posix_assert(URCU_TLS(rcu_reader).need_mb == 0);
483 urcu_posix_assert(!(URCU_TLS(rcu_reader).ctr & URCU_GP_CTR_NEST_MASK));
02be5561 484
731ccb96 485 mutex_lock(&rcu_registry_lock);
01477510 486 urcu_posix_assert(!URCU_TLS(rcu_reader).registered);
a77f7d82 487 URCU_TLS(rcu_reader).registered = 1;
02be5561 488 rcu_init(); /* In case gcc does not support constructor attribute */
bd252a04 489 cds_list_add(&URCU_TLS(rcu_reader).node, &registry);
731ccb96 490 mutex_unlock(&rcu_registry_lock);
27b012e2
MD
491}
492
121a5d44 493void rcu_unregister_thread(void)
27b012e2 494{
731ccb96 495 mutex_lock(&rcu_registry_lock);
01477510 496 urcu_posix_assert(URCU_TLS(rcu_reader).registered);
a77f7d82 497 URCU_TLS(rcu_reader).registered = 0;
bd252a04 498 cds_list_del(&URCU_TLS(rcu_reader).node);
731ccb96 499 mutex_unlock(&rcu_registry_lock);
27b012e2
MD
500}
501
fdf01eed 502#ifdef RCU_MEMBARRIER
d8d9a340
MD
503
504#ifdef CONFIG_RCU_FORCE_SYS_MEMBARRIER
505static
c0bb9f69 506void rcu_sys_membarrier_status(bool available)
d8d9a340
MD
507{
508 if (!available)
509 abort();
510}
511#else
512static
c0bb9f69 513void rcu_sys_membarrier_status(bool available)
d8d9a340 514{
c0bb9f69
MD
515 if (!available)
516 return;
4477a870 517 urcu_memb_has_sys_membarrier = 1;
d8d9a340
MD
518}
519#endif
520
c0bb9f69
MD
521static
522void rcu_sys_membarrier_init(void)
fdf01eed 523{
c0bb9f69
MD
524 bool available = false;
525 int mask;
526
527 mask = membarrier(MEMBARRIER_CMD_QUERY, 0);
528 if (mask >= 0) {
529 if (mask & MEMBARRIER_CMD_PRIVATE_EXPEDITED) {
530 if (membarrier(MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED, 0))
531 urcu_die(errno);
4477a870 532 urcu_memb_has_sys_membarrier_private_expedited = 1;
c0bb9f69
MD
533 available = true;
534 } else if (mask & MEMBARRIER_CMD_SHARED) {
535 available = true;
536 }
537 }
538 rcu_sys_membarrier_status(available);
539}
64f469e6 540
c0bb9f69
MD
541void rcu_init(void)
542{
fdf01eed
MD
543 if (init_done)
544 return;
545 init_done = 1;
c0bb9f69 546 rcu_sys_membarrier_init();
fdf01eed
MD
547}
548#endif
549
02be5561 550void rcu_exit(void)
27b012e2 551{
90f72b8c 552 urcu_call_rcu_exit();
27b012e2 553}
5e77fc1f 554
5e6b23a6 555DEFINE_RCU_FLAVOR(rcu_flavor);
541d828d 556
5e77fc1f 557#include "urcu-call-rcu-impl.h"
0376e7b2 558#include "urcu-defer-impl.h"
111bda8f 559#include "urcu-poll-impl.h"
This page took 0.090279 seconds and 4 git commands to generate.