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