Port: no symbols aliases on MacOS
[urcu.git] / src / urcu.c
1 /*
2 * urcu.c
3 *
4 * Userspace RCU 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 _BSD_SOURCE
27 #define _LGPL_SOURCE
28 #define _DEFAULT_SOURCE
29 #include <stdio.h>
30 #include <pthread.h>
31 #include <signal.h>
32 #include <assert.h>
33 #include <stdlib.h>
34 #include <stdint.h>
35 #include <string.h>
36 #include <errno.h>
37 #include <stdbool.h>
38 #include <poll.h>
39
40 #include <urcu/arch.h>
41 #include <urcu/wfcqueue.h>
42 #include <urcu/map/urcu.h>
43 #include <urcu/static/urcu.h>
44 #include <urcu/pointer.h>
45 #include <urcu/tls-compat.h>
46
47 #include "urcu-die.h"
48 #include "urcu-wait.h"
49 #include "urcu-utils.h"
50
51 #define URCU_API_MAP
52 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
53 #undef _LGPL_SOURCE
54 #include <urcu/urcu.h>
55 #define _LGPL_SOURCE
56
57 /*
58 * If a reader is really non-cooperative and refuses to commit its
59 * rcu_active_readers count to memory (there is no barrier in the reader
60 * per-se), kick it after 10 loops waiting for it.
61 */
62 #define KICK_READER_LOOPS 10
63
64 /*
65 * Active attempts to check for reader Q.S. before calling futex().
66 */
67 #define RCU_QS_ACTIVE_ATTEMPTS 100
68
69 /* If the headers do not support membarrier system call, fall back on RCU_MB */
70 #ifdef __NR_membarrier
71 # define membarrier(...) syscall(__NR_membarrier, __VA_ARGS__)
72 #else
73 # define membarrier(...) -ENOSYS
74 #endif
75
76 enum membarrier_cmd {
77 MEMBARRIER_CMD_QUERY = 0,
78 MEMBARRIER_CMD_SHARED = (1 << 0),
79 /* reserved for MEMBARRIER_CMD_SHARED_EXPEDITED (1 << 1) */
80 /* reserved for MEMBARRIER_CMD_PRIVATE (1 << 2) */
81 MEMBARRIER_CMD_PRIVATE_EXPEDITED = (1 << 3),
82 MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED = (1 << 4),
83 };
84
85 #ifdef RCU_MEMBARRIER
86 static int init_done;
87 static int urcu_memb_has_sys_membarrier_private_expedited;
88
89 #ifndef CONFIG_RCU_FORCE_SYS_MEMBARRIER
90 /*
91 * Explicitly initialize to zero because we can't alias a non-static
92 * uninitialized variable.
93 */
94 int urcu_memb_has_sys_membarrier = 0;
95 URCU_ATTR_ALIAS("urcu_memb_has_sys_membarrier")
96 extern int rcu_has_sys_membarrier_memb;
97 #endif
98
99 void __attribute__((constructor)) rcu_init(void);
100 #endif
101
102 #ifdef RCU_MB
103 void rcu_init(void)
104 {
105 }
106 URCU_ATTR_ALIAS(urcu_stringify(rcu_init))
107 void alias_rcu_init(void);
108 #endif
109
110 #ifdef RCU_SIGNAL
111 static int init_done;
112
113 void __attribute__((constructor)) rcu_init(void);
114 void __attribute__((destructor)) rcu_exit(void);
115 #endif
116
117 /*
118 * rcu_gp_lock ensures mutual exclusion between threads calling
119 * synchronize_rcu().
120 */
121 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
122 /*
123 * rcu_registry_lock ensures mutual exclusion between threads
124 * registering and unregistering themselves to/from the registry, and
125 * with threads reading that registry from synchronize_rcu(). However,
126 * this lock is not held all the way through the completion of awaiting
127 * for the grace period. It is sporadically released between iterations
128 * on the registry.
129 * rcu_registry_lock may nest inside rcu_gp_lock.
130 */
131 static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
132 struct urcu_gp rcu_gp = { .ctr = URCU_GP_COUNT };
133 URCU_ATTR_ALIAS(urcu_stringify(rcu_gp))
134 extern struct urcu_gp alias_rcu_gp;
135
136 /*
137 * Written to only by each individual reader. Read by both the reader and the
138 * writers.
139 */
140 DEFINE_URCU_TLS(struct urcu_reader, rcu_reader);
141 URCU_ATTR_ALIAS(urcu_stringify(rcu_reader))
142 extern struct urcu_reader alias_rcu_reader;
143
144 static CDS_LIST_HEAD(registry);
145
146 /*
147 * Queue keeping threads awaiting to wait for a grace period. Contains
148 * struct gp_waiters_thread objects.
149 */
150 static DEFINE_URCU_WAIT_QUEUE(gp_waiters);
151
152 static void mutex_lock(pthread_mutex_t *mutex)
153 {
154 int ret;
155
156 #ifndef DISTRUST_SIGNALS_EXTREME
157 ret = pthread_mutex_lock(mutex);
158 if (ret)
159 urcu_die(ret);
160 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
161 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
162 if (ret != EBUSY && ret != EINTR)
163 urcu_die(ret);
164 if (CMM_LOAD_SHARED(URCU_TLS(rcu_reader).need_mb)) {
165 cmm_smp_mb();
166 _CMM_STORE_SHARED(URCU_TLS(rcu_reader).need_mb, 0);
167 cmm_smp_mb();
168 }
169 (void) poll(NULL, 0, 10);
170 }
171 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
172 }
173
174 static void mutex_unlock(pthread_mutex_t *mutex)
175 {
176 int ret;
177
178 ret = pthread_mutex_unlock(mutex);
179 if (ret)
180 urcu_die(ret);
181 }
182
183 #ifdef RCU_MEMBARRIER
184 static void smp_mb_master(void)
185 {
186 if (caa_likely(urcu_memb_has_sys_membarrier)) {
187 if (membarrier(urcu_memb_has_sys_membarrier_private_expedited ?
188 MEMBARRIER_CMD_PRIVATE_EXPEDITED :
189 MEMBARRIER_CMD_SHARED, 0))
190 urcu_die(errno);
191 } else {
192 cmm_smp_mb();
193 }
194 }
195 #endif
196
197 #ifdef RCU_MB
198 static void smp_mb_master(void)
199 {
200 cmm_smp_mb();
201 }
202 #endif
203
204 #ifdef RCU_SIGNAL
205 static void force_mb_all_readers(void)
206 {
207 struct urcu_reader *index;
208
209 /*
210 * Ask for each threads to execute a cmm_smp_mb() so we can consider the
211 * compiler barriers around rcu read lock as real memory barriers.
212 */
213 if (cds_list_empty(&registry))
214 return;
215 /*
216 * pthread_kill has a cmm_smp_mb(). But beware, we assume it performs
217 * a cache flush on architectures with non-coherent cache. Let's play
218 * safe and don't assume anything : we use cmm_smp_mc() to make sure the
219 * cache flush is enforced.
220 */
221 cds_list_for_each_entry(index, &registry, node) {
222 CMM_STORE_SHARED(index->need_mb, 1);
223 pthread_kill(index->tid, SIGRCU);
224 }
225 /*
226 * Wait for sighandler (and thus mb()) to execute on every thread.
227 *
228 * Note that the pthread_kill() will never be executed on systems
229 * that correctly deliver signals in a timely manner. However, it
230 * is not uncommon for kernels to have bugs that can result in
231 * lost or unduly delayed signals.
232 *
233 * If you are seeing the below pthread_kill() executing much at
234 * all, we suggest testing the underlying kernel and filing the
235 * relevant bug report. For Linux kernels, we recommend getting
236 * the Linux Test Project (LTP).
237 */
238 cds_list_for_each_entry(index, &registry, node) {
239 while (CMM_LOAD_SHARED(index->need_mb)) {
240 pthread_kill(index->tid, SIGRCU);
241 (void) poll(NULL, 0, 1);
242 }
243 }
244 cmm_smp_mb(); /* read ->need_mb before ending the barrier */
245 }
246
247 static void smp_mb_master(void)
248 {
249 force_mb_all_readers();
250 }
251 #endif /* #ifdef RCU_SIGNAL */
252
253 /*
254 * synchronize_rcu() waiting. Single thread.
255 * Always called with rcu_registry lock held. Releases this lock and
256 * grabs it again. Holds the lock when it returns.
257 */
258 static void wait_gp(void)
259 {
260 /*
261 * Read reader_gp before read futex. smp_mb_master() needs to
262 * be called with the rcu registry lock held in RCU_SIGNAL
263 * flavor.
264 */
265 smp_mb_master();
266 /* Temporarily unlock the registry lock. */
267 mutex_unlock(&rcu_registry_lock);
268 if (uatomic_read(&rcu_gp.futex) != -1)
269 goto end;
270 while (futex_async(&rcu_gp.futex, FUTEX_WAIT, -1,
271 NULL, NULL, 0)) {
272 switch (errno) {
273 case EWOULDBLOCK:
274 /* Value already changed. */
275 goto end;
276 case EINTR:
277 /* Retry if interrupted by signal. */
278 break; /* Get out of switch. */
279 default:
280 /* Unexpected error. */
281 urcu_die(errno);
282 }
283 }
284 end:
285 /*
286 * Re-lock the registry lock before the next loop.
287 */
288 mutex_lock(&rcu_registry_lock);
289 }
290
291 /*
292 * Always called with rcu_registry lock held. Releases this lock between
293 * iterations and grabs it again. Holds the lock when it returns.
294 */
295 static void wait_for_readers(struct cds_list_head *input_readers,
296 struct cds_list_head *cur_snap_readers,
297 struct cds_list_head *qsreaders)
298 {
299 unsigned int wait_loops = 0;
300 struct urcu_reader *index, *tmp;
301 #ifdef HAS_INCOHERENT_CACHES
302 unsigned int wait_gp_loops = 0;
303 #endif /* HAS_INCOHERENT_CACHES */
304
305 /*
306 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
307 * indicate quiescence (not nested), or observe the current
308 * rcu_gp.ctr value.
309 */
310 for (;;) {
311 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
312 wait_loops++;
313 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
314 uatomic_dec(&rcu_gp.futex);
315 /* Write futex before read reader_gp */
316 smp_mb_master();
317 }
318
319 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
320 switch (urcu_common_reader_state(&rcu_gp, &index->ctr)) {
321 case URCU_READER_ACTIVE_CURRENT:
322 if (cur_snap_readers) {
323 cds_list_move(&index->node,
324 cur_snap_readers);
325 break;
326 }
327 /* Fall-through */
328 case URCU_READER_INACTIVE:
329 cds_list_move(&index->node, qsreaders);
330 break;
331 case URCU_READER_ACTIVE_OLD:
332 /*
333 * Old snapshot. Leaving node in
334 * input_readers will make us busy-loop
335 * until the snapshot becomes current or
336 * the reader becomes inactive.
337 */
338 break;
339 }
340 }
341
342 #ifndef HAS_INCOHERENT_CACHES
343 if (cds_list_empty(input_readers)) {
344 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
345 /* Read reader_gp before write futex */
346 smp_mb_master();
347 uatomic_set(&rcu_gp.futex, 0);
348 }
349 break;
350 } else {
351 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
352 /* wait_gp unlocks/locks registry lock. */
353 wait_gp();
354 } else {
355 /* Temporarily unlock the registry lock. */
356 mutex_unlock(&rcu_registry_lock);
357 caa_cpu_relax();
358 /*
359 * Re-lock the registry lock before the
360 * next loop.
361 */
362 mutex_lock(&rcu_registry_lock);
363 }
364 }
365 #else /* #ifndef HAS_INCOHERENT_CACHES */
366 /*
367 * BUSY-LOOP. Force the reader thread to commit its
368 * URCU_TLS(rcu_reader).ctr update to memory if we wait
369 * for too long.
370 */
371 if (cds_list_empty(input_readers)) {
372 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
373 /* Read reader_gp before write futex */
374 smp_mb_master();
375 uatomic_set(&rcu_gp.futex, 0);
376 }
377 break;
378 } else {
379 if (wait_gp_loops == KICK_READER_LOOPS) {
380 smp_mb_master();
381 wait_gp_loops = 0;
382 }
383 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS) {
384 /* wait_gp unlocks/locks registry lock. */
385 wait_gp();
386 wait_gp_loops++;
387 } else {
388 /* Temporarily unlock the registry lock. */
389 mutex_unlock(&rcu_registry_lock);
390 caa_cpu_relax();
391 /*
392 * Re-lock the registry lock before the
393 * next loop.
394 */
395 mutex_lock(&rcu_registry_lock);
396 }
397 }
398 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
399 }
400 }
401
402 void synchronize_rcu(void)
403 {
404 CDS_LIST_HEAD(cur_snap_readers);
405 CDS_LIST_HEAD(qsreaders);
406 DEFINE_URCU_WAIT_NODE(wait, URCU_WAIT_WAITING);
407 struct urcu_waiters waiters;
408
409 /*
410 * Add ourself to gp_waiters queue of threads awaiting to wait
411 * for a grace period. Proceed to perform the grace period only
412 * if we are the first thread added into the queue.
413 * The implicit memory barrier before urcu_wait_add()
414 * orders prior memory accesses of threads put into the wait
415 * queue before their insertion into the wait queue.
416 */
417 if (urcu_wait_add(&gp_waiters, &wait) != 0) {
418 /* Not first in queue: will be awakened by another thread. */
419 urcu_adaptative_busy_wait(&wait);
420 /* Order following memory accesses after grace period. */
421 cmm_smp_mb();
422 return;
423 }
424 /* We won't need to wake ourself up */
425 urcu_wait_set_state(&wait, URCU_WAIT_RUNNING);
426
427 mutex_lock(&rcu_gp_lock);
428
429 /*
430 * Move all waiters into our local queue.
431 */
432 urcu_move_waiters(&waiters, &gp_waiters);
433
434 mutex_lock(&rcu_registry_lock);
435
436 if (cds_list_empty(&registry))
437 goto out;
438
439 /*
440 * All threads should read qparity before accessing data structure
441 * where new ptr points to. Must be done within rcu_registry_lock
442 * because it iterates on reader threads.
443 */
444 /* Write new ptr before changing the qparity */
445 smp_mb_master();
446
447 /*
448 * Wait for readers to observe original parity or be quiescent.
449 * wait_for_readers() can release and grab again rcu_registry_lock
450 * interally.
451 */
452 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
453
454 /*
455 * Must finish waiting for quiescent state for original parity before
456 * committing next rcu_gp.ctr update to memory. Failure to do so could
457 * result in the writer waiting forever while new readers are always
458 * accessing data (no progress). Enforce compiler-order of load
459 * URCU_TLS(rcu_reader).ctr before store to rcu_gp.ctr.
460 */
461 cmm_barrier();
462
463 /*
464 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
465 * model easier to understand. It does not have a big performance impact
466 * anyway, given this is the write-side.
467 */
468 cmm_smp_mb();
469
470 /* Switch parity: 0 -> 1, 1 -> 0 */
471 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr ^ URCU_GP_CTR_PHASE);
472
473 /*
474 * Must commit rcu_gp.ctr update to memory before waiting for quiescent
475 * state. Failure to do so could result in the writer waiting forever
476 * while new readers are always accessing data (no progress). Enforce
477 * compiler-order of store to rcu_gp.ctr before load rcu_reader ctr.
478 */
479 cmm_barrier();
480
481 /*
482 *
483 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
484 * model easier to understand. It does not have a big performance impact
485 * anyway, given this is the write-side.
486 */
487 cmm_smp_mb();
488
489 /*
490 * Wait for readers to observe new parity or be quiescent.
491 * wait_for_readers() can release and grab again rcu_registry_lock
492 * interally.
493 */
494 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
495
496 /*
497 * Put quiescent reader list back into registry.
498 */
499 cds_list_splice(&qsreaders, &registry);
500
501 /*
502 * Finish waiting for reader threads before letting the old ptr
503 * being freed. Must be done within rcu_registry_lock because it
504 * iterates on reader threads.
505 */
506 smp_mb_master();
507 out:
508 mutex_unlock(&rcu_registry_lock);
509 mutex_unlock(&rcu_gp_lock);
510
511 /*
512 * Wakeup waiters only after we have completed the grace period
513 * and have ensured the memory barriers at the end of the grace
514 * period have been issued.
515 */
516 urcu_wake_all_waiters(&waiters);
517 }
518 URCU_ATTR_ALIAS(urcu_stringify(synchronize_rcu))
519 void alias_synchronize_rcu();
520
521 /*
522 * library wrappers to be used by non-LGPL compatible source code.
523 */
524
525 void rcu_read_lock(void)
526 {
527 _rcu_read_lock();
528 }
529 URCU_ATTR_ALIAS(urcu_stringify(rcu_read_lock))
530 void alias_rcu_read_lock();
531
532 void rcu_read_unlock(void)
533 {
534 _rcu_read_unlock();
535 }
536 URCU_ATTR_ALIAS(urcu_stringify(rcu_read_unlock))
537 void alias_rcu_read_unlock();
538
539 int rcu_read_ongoing(void)
540 {
541 return _rcu_read_ongoing();
542 }
543 URCU_ATTR_ALIAS(urcu_stringify(rcu_read_ongoing))
544 void alias_rcu_read_ongoing();
545
546 void rcu_register_thread(void)
547 {
548 URCU_TLS(rcu_reader).tid = pthread_self();
549 assert(URCU_TLS(rcu_reader).need_mb == 0);
550 assert(!(URCU_TLS(rcu_reader).ctr & URCU_GP_CTR_NEST_MASK));
551
552 mutex_lock(&rcu_registry_lock);
553 assert(!URCU_TLS(rcu_reader).registered);
554 URCU_TLS(rcu_reader).registered = 1;
555 rcu_init(); /* In case gcc does not support constructor attribute */
556 cds_list_add(&URCU_TLS(rcu_reader).node, &registry);
557 mutex_unlock(&rcu_registry_lock);
558 }
559 URCU_ATTR_ALIAS(urcu_stringify(rcu_register_thread))
560 void alias_rcu_register_thread();
561
562 void rcu_unregister_thread(void)
563 {
564 mutex_lock(&rcu_registry_lock);
565 assert(URCU_TLS(rcu_reader).registered);
566 URCU_TLS(rcu_reader).registered = 0;
567 cds_list_del(&URCU_TLS(rcu_reader).node);
568 mutex_unlock(&rcu_registry_lock);
569 }
570 URCU_ATTR_ALIAS(urcu_stringify(rcu_unregister_thread))
571 void alias_rcu_unregister_thread();
572
573 #ifdef RCU_MEMBARRIER
574
575 #ifdef CONFIG_RCU_FORCE_SYS_MEMBARRIER
576 static
577 void rcu_sys_membarrier_status(bool available)
578 {
579 if (!available)
580 abort();
581 }
582 #else
583 static
584 void rcu_sys_membarrier_status(bool available)
585 {
586 if (!available)
587 return;
588 urcu_memb_has_sys_membarrier = 1;
589 }
590 #endif
591
592 static
593 void rcu_sys_membarrier_init(void)
594 {
595 bool available = false;
596 int mask;
597
598 mask = membarrier(MEMBARRIER_CMD_QUERY, 0);
599 if (mask >= 0) {
600 if (mask & MEMBARRIER_CMD_PRIVATE_EXPEDITED) {
601 if (membarrier(MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED, 0))
602 urcu_die(errno);
603 urcu_memb_has_sys_membarrier_private_expedited = 1;
604 available = true;
605 } else if (mask & MEMBARRIER_CMD_SHARED) {
606 available = true;
607 }
608 }
609 rcu_sys_membarrier_status(available);
610 }
611
612 void rcu_init(void)
613 {
614 if (init_done)
615 return;
616 init_done = 1;
617 rcu_sys_membarrier_init();
618 }
619 URCU_ATTR_ALIAS(urcu_stringify(rcu_init))
620 void alias_rcu_init(void);
621 #endif
622
623 #ifdef RCU_SIGNAL
624 static void sigrcu_handler(int signo, siginfo_t *siginfo, void *context)
625 {
626 /*
627 * Executing this cmm_smp_mb() is the only purpose of this signal handler.
628 * It punctually promotes cmm_barrier() into cmm_smp_mb() on every thread it is
629 * executed on.
630 */
631 cmm_smp_mb();
632 _CMM_STORE_SHARED(URCU_TLS(rcu_reader).need_mb, 0);
633 cmm_smp_mb();
634 }
635
636 /*
637 * rcu_init constructor. Called when the library is linked, but also when
638 * reader threads are calling rcu_register_thread().
639 * Should only be called by a single thread at a given time. This is ensured by
640 * holing the rcu_registry_lock from rcu_register_thread() or by running
641 * at library load time, which should not be executed by multiple
642 * threads nor concurrently with rcu_register_thread() anyway.
643 */
644 void rcu_init(void)
645 {
646 struct sigaction act;
647 int ret;
648
649 if (init_done)
650 return;
651 init_done = 1;
652
653 act.sa_sigaction = sigrcu_handler;
654 act.sa_flags = SA_SIGINFO | SA_RESTART;
655 sigemptyset(&act.sa_mask);
656 ret = sigaction(SIGRCU, &act, NULL);
657 if (ret)
658 urcu_die(errno);
659 }
660 URCU_ATTR_ALIAS(urcu_stringify(rcu_init))
661 void alias_rcu_init(void);
662
663 void rcu_exit(void)
664 {
665 /*
666 * Don't unregister the SIGRCU signal handler anymore, because
667 * call_rcu threads could still be using it shortly before the
668 * application exits.
669 * Assertion disabled because call_rcu threads are now rcu
670 * readers, and left running at exit.
671 * assert(cds_list_empty(&registry));
672 */
673 }
674 URCU_ATTR_ALIAS(urcu_stringify(rcu_exit))
675 void alias_rcu_exit(void);
676
677 #endif /* #ifdef RCU_SIGNAL */
678
679 DEFINE_RCU_FLAVOR(rcu_flavor);
680 DEFINE_RCU_FLAVOR_ALIAS(rcu_flavor, alias_rcu_flavor);
681
682 #include "urcu-call-rcu-impl.h"
683 #include "urcu-defer-impl.h"
This page took 0.058126 seconds and 4 git commands to generate.