1 // SPDX-FileCopyrightText: 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2 // SPDX-FileCopyrightText: 2009 Paul E. McKenney, IBM Corporation.
4 // SPDX-License-Identifier: LGPL-2.1-or-later
7 * Userspace RCU library
9 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
12 #define URCU_NO_COMPAT_IDENTIFIERS
15 #define _DEFAULT_SOURCE
26 #include <urcu/config.h>
27 #include <urcu/annotate.h>
28 #include <urcu/assert.h>
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>
37 #include "urcu-wait.h"
38 #include "urcu-utils.h"
41 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
43 #include <urcu/urcu.h>
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
49 * per-se), kick it after 10 loops waiting for it.
51 #define KICK_READER_LOOPS 10
54 * Active attempts to check for reader Q.S. before calling futex().
56 #define RCU_QS_ACTIVE_ATTEMPTS 100
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__)
62 # define membarrier(...) -ENOSYS
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),
76 static int urcu_memb_has_sys_membarrier_private_expedited
;
78 #ifndef CONFIG_RCU_FORCE_SYS_MEMBARRIER
80 * Explicitly initialize to zero because we can't alias a non-static
81 * uninitialized variable.
83 int urcu_memb_has_sys_membarrier
= 0;
86 void __attribute__((constructor
)) rcu_init(void);
89 #if defined(RCU_MB) || defined(RCU_SIGNAL)
95 void __attribute__((destructor
)) rcu_exit(void);
96 static void urcu_call_rcu_exit(void);
99 * rcu_gp_lock ensures mutual exclusion between threads calling
102 static pthread_mutex_t rcu_gp_lock
= PTHREAD_MUTEX_INITIALIZER
;
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
110 * rcu_registry_lock may nest inside rcu_gp_lock.
112 static pthread_mutex_t rcu_registry_lock
= PTHREAD_MUTEX_INITIALIZER
;
113 struct urcu_gp rcu_gp
= { .ctr
= URCU_GP_COUNT
};
116 * Written to only by each individual reader. Read by both the reader and the
119 DEFINE_URCU_TLS(struct urcu_reader
, rcu_reader
);
121 static CDS_LIST_HEAD(registry
);
124 * Queue keeping threads awaiting to wait for a grace period. Contains
125 * struct gp_waiters_thread objects.
127 static DEFINE_URCU_WAIT_QUEUE(gp_waiters
);
129 static void mutex_lock(pthread_mutex_t
*mutex
)
133 #ifndef DISTRUST_SIGNALS_EXTREME
134 ret
= pthread_mutex_lock(mutex
);
137 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
138 while ((ret
= pthread_mutex_trylock(mutex
)) != 0) {
139 if (ret
!= EBUSY
&& ret
!= EINTR
)
141 if (CMM_LOAD_SHARED(URCU_TLS(rcu_reader
).need_mb
)) {
143 _CMM_STORE_SHARED(URCU_TLS(rcu_reader
).need_mb
, 0);
146 (void) poll(NULL
, 0, 10);
148 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
151 static void mutex_unlock(pthread_mutex_t
*mutex
)
155 ret
= pthread_mutex_unlock(mutex
);
160 #ifdef RCU_MEMBARRIER
161 static void smp_mb_master(void)
163 if (caa_likely(urcu_memb_has_sys_membarrier
)) {
164 if (membarrier(urcu_memb_has_sys_membarrier_private_expedited
?
165 MEMBARRIER_CMD_PRIVATE_EXPEDITED
:
166 MEMBARRIER_CMD_SHARED
, 0))
174 #if defined(RCU_MB) || defined(RCU_SIGNAL)
175 static void smp_mb_master(void)
182 * synchronize_rcu() waiting. Single thread.
183 * Always called with rcu_registry lock held. Releases this lock and
184 * grabs it again. Holds the lock when it returns.
186 static void wait_gp(void)
189 * Read reader_gp before read futex.
192 /* Temporarily unlock the registry lock. */
193 mutex_unlock(&rcu_registry_lock
);
194 while (uatomic_read(&rcu_gp
.futex
) == -1) {
195 if (!futex_async(&rcu_gp
.futex
, FUTEX_WAIT
, -1, NULL
, NULL
, 0)) {
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
208 /* Value already changed. */
211 /* Retry if interrupted by signal. */
212 break; /* Get out of switch. Check again. */
214 /* Unexpected error. */
220 * Re-lock the registry lock before the next loop.
222 mutex_lock(&rcu_registry_lock
);
226 * Always called with rcu_registry lock held. Releases this lock between
227 * iterations and grabs it again. Holds the lock when it returns.
229 static void wait_for_readers(struct cds_list_head
*input_readers
,
230 struct cds_list_head
*cur_snap_readers
,
231 struct cds_list_head
*qsreaders
,
232 cmm_annotate_t
*group
)
234 unsigned int wait_loops
= 0;
235 struct urcu_reader
*index
, *tmp
;
236 #ifdef HAS_INCOHERENT_CACHES
237 unsigned int wait_gp_loops
= 0;
238 #endif /* HAS_INCOHERENT_CACHES */
241 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
242 * indicate quiescence (not nested), or observe the current
246 if (wait_loops
< RCU_QS_ACTIVE_ATTEMPTS
)
248 if (wait_loops
>= RCU_QS_ACTIVE_ATTEMPTS
) {
249 uatomic_dec(&rcu_gp
.futex
);
250 /* Write futex before read reader_gp */
254 cds_list_for_each_entry_safe(index
, tmp
, input_readers
, node
) {
255 switch (urcu_common_reader_state(&rcu_gp
, &index
->ctr
, group
)) {
256 case URCU_READER_ACTIVE_CURRENT
:
257 if (cur_snap_readers
) {
258 cds_list_move(&index
->node
,
263 case URCU_READER_INACTIVE
:
264 cds_list_move(&index
->node
, qsreaders
);
266 case URCU_READER_ACTIVE_OLD
:
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.
277 #ifndef HAS_INCOHERENT_CACHES
278 if (cds_list_empty(input_readers
)) {
279 if (wait_loops
>= RCU_QS_ACTIVE_ATTEMPTS
) {
280 /* Read reader_gp before write futex */
282 uatomic_set(&rcu_gp
.futex
, 0);
286 if (wait_loops
>= RCU_QS_ACTIVE_ATTEMPTS
) {
287 /* wait_gp unlocks/locks registry lock. */
290 /* Temporarily unlock the registry lock. */
291 mutex_unlock(&rcu_registry_lock
);
294 * Re-lock the registry lock before the
297 mutex_lock(&rcu_registry_lock
);
300 #else /* #ifndef HAS_INCOHERENT_CACHES */
302 * BUSY-LOOP. Force the reader thread to commit its
303 * URCU_TLS(rcu_reader).ctr update to memory if we wait
306 if (cds_list_empty(input_readers
)) {
307 if (wait_loops
>= RCU_QS_ACTIVE_ATTEMPTS
) {
308 /* Read reader_gp before write futex */
310 uatomic_set(&rcu_gp
.futex
, 0);
314 if (wait_gp_loops
== KICK_READER_LOOPS
) {
318 if (wait_loops
>= RCU_QS_ACTIVE_ATTEMPTS
) {
319 /* wait_gp unlocks/locks registry lock. */
323 /* Temporarily unlock the registry lock. */
324 mutex_unlock(&rcu_registry_lock
);
327 * Re-lock the registry lock before the
330 mutex_lock(&rcu_registry_lock
);
333 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
337 void synchronize_rcu(void)
339 cmm_annotate_define(acquire_group
);
340 cmm_annotate_define(release_group
);
341 CDS_LIST_HEAD(cur_snap_readers
);
342 CDS_LIST_HEAD(qsreaders
);
343 DEFINE_URCU_WAIT_NODE(wait
, URCU_WAIT_WAITING
);
344 struct urcu_waiters waiters
;
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.
354 if (urcu_wait_add(&gp_waiters
, &wait
) != 0) {
356 * Not first in queue: will be awakened by another thread.
357 * Implies a memory barrier after grace period.
359 urcu_adaptative_busy_wait(&wait
);
362 /* We won't need to wake ourself up */
363 urcu_wait_set_state(&wait
, URCU_WAIT_RUNNING
);
365 mutex_lock(&rcu_gp_lock
);
368 * Move all waiters into our local queue.
370 urcu_move_waiters(&waiters
, &gp_waiters
);
372 mutex_lock(&rcu_registry_lock
);
374 if (cds_list_empty(®istry
))
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.
382 /* Write new ptr before changing the qparity */
384 cmm_annotate_group_mb_release(&release_group
);
387 * Wait for readers to observe original parity or be quiescent.
388 * wait_for_readers() can release and grab again rcu_registry_lock
391 wait_for_readers(®istry
, &cur_snap_readers
, &qsreaders
, &acquire_group
);
394 * Must finish waiting for quiescent state for original parity before
395 * committing next rcu_gp.ctr update to memory. Failure to do so could
396 * result in the writer waiting forever while new readers are always
397 * accessing data (no progress). Enforce compiler-order of load
398 * URCU_TLS(rcu_reader).ctr before store to rcu_gp.ctr.
403 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
404 * model easier to understand. It does not have a big performance impact
405 * anyway, given this is the write-side.
409 /* Switch parity: 0 -> 1, 1 -> 0 */
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
);
414 * Must commit rcu_gp.ctr update to memory before waiting for quiescent
415 * state. Failure to do so could result in the writer waiting forever
416 * while new readers are always accessing data (no progress). Enforce
417 * compiler-order of store to rcu_gp.ctr before load rcu_reader ctr.
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.
430 * Wait for readers to observe new parity or be quiescent.
431 * wait_for_readers() can release and grab again rcu_registry_lock
434 wait_for_readers(&cur_snap_readers
, NULL
, &qsreaders
, &acquire_group
);
437 * Put quiescent reader list back into registry.
439 cds_list_splice(&qsreaders
, ®istry
);
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.
447 cmm_annotate_group_mb_acquire(&acquire_group
);
449 mutex_unlock(&rcu_registry_lock
);
450 mutex_unlock(&rcu_gp_lock
);
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.
457 urcu_wake_all_waiters(&waiters
);
461 * library wrappers to be used by non-LGPL compatible source code.
464 void rcu_read_lock(void)
469 void rcu_read_unlock(void)
474 int rcu_read_ongoing(void)
476 return _rcu_read_ongoing();
479 void rcu_register_thread(void)
481 URCU_TLS(rcu_reader
).tid
= pthread_self();
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
));
485 mutex_lock(&rcu_registry_lock
);
486 urcu_posix_assert(!URCU_TLS(rcu_reader
).registered
);
487 URCU_TLS(rcu_reader
).registered
= 1;
488 rcu_init(); /* In case gcc does not support constructor attribute */
489 cds_list_add(&URCU_TLS(rcu_reader
).node
, ®istry
);
490 mutex_unlock(&rcu_registry_lock
);
493 void rcu_unregister_thread(void)
495 mutex_lock(&rcu_registry_lock
);
496 urcu_posix_assert(URCU_TLS(rcu_reader
).registered
);
497 URCU_TLS(rcu_reader
).registered
= 0;
498 cds_list_del(&URCU_TLS(rcu_reader
).node
);
499 mutex_unlock(&rcu_registry_lock
);
502 #ifdef RCU_MEMBARRIER
504 #ifdef CONFIG_RCU_FORCE_SYS_MEMBARRIER
506 void rcu_sys_membarrier_status(bool available
)
513 void rcu_sys_membarrier_status(bool available
)
517 urcu_memb_has_sys_membarrier
= 1;
522 void rcu_sys_membarrier_init(void)
524 bool available
= false;
527 mask
= membarrier(MEMBARRIER_CMD_QUERY
, 0);
529 if (mask
& MEMBARRIER_CMD_PRIVATE_EXPEDITED
) {
530 if (membarrier(MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED
, 0))
532 urcu_memb_has_sys_membarrier_private_expedited
= 1;
534 } else if (mask
& MEMBARRIER_CMD_SHARED
) {
538 rcu_sys_membarrier_status(available
);
546 rcu_sys_membarrier_init();
552 urcu_call_rcu_exit();
555 DEFINE_RCU_FLAVOR(rcu_flavor
);
557 #include "urcu-call-rcu-impl.h"
558 #include "urcu-defer-impl.h"
559 #include "urcu-poll-impl.h"