4 * Userspace RCU library
6 * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
8 * Distributed under LGPLv2.1
10 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
22 #include "urcu-static.h"
23 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
26 pthread_mutex_t urcu_mutex
= PTHREAD_MUTEX_INITIALIZER
;
29 * Global grace period counter.
30 * Contains the current RCU_GP_CTR_BIT.
31 * Also has a RCU_GP_CTR_BIT of 1, to accelerate the reader fast path.
32 * Written to only by writer with mutex taken. Read by both writer and readers.
34 long urcu_gp_ctr
= RCU_GP_COUNT
;
37 * Written to only by each individual reader. Read by both the reader and the
40 long __thread urcu_active_readers
;
42 /* Thread IDs of registered readers */
43 #define INIT_NUM_THREADS 4
45 struct reader_registry
{
47 long *urcu_active_readers
;
52 unsigned int yield_active
;
53 unsigned int __thread rand_yield
;
56 static struct reader_registry
*registry
;
57 static char __thread need_mb
;
58 static int num_readers
, alloc_readers
;
60 void internal_urcu_lock(void)
64 #ifndef DISTRUST_SIGNALS_EXTREME
65 ret
= pthread_mutex_lock(&urcu_mutex
);
67 perror("Error in pthread mutex lock");
70 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
71 while ((ret
= pthread_mutex_trylock(&urcu_mutex
)) != 0) {
72 if (ret
!= EBUSY
&& ret
!= EINTR
) {
73 printf("ret = %d, errno = %d\n", ret
, errno
);
74 perror("Error in pthread mutex lock");
84 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
87 void internal_urcu_unlock(void)
91 ret
= pthread_mutex_unlock(&urcu_mutex
);
93 perror("Error in pthread mutex unlock");
99 * called with urcu_mutex held.
101 static void switch_next_urcu_qparity(void)
103 STORE_SHARED(urcu_gp_ctr
, urcu_gp_ctr
^ RCU_GP_CTR_BIT
);
107 #ifdef HAS_INCOHERENT_CACHES
108 static void force_mb_single_thread(struct reader_registry
*index
)
112 #endif /* #ifdef HAS_INCOHERENT_CACHES */
114 static void force_mb_all_threads(void)
118 #else /* #ifdef DEBUG_FULL_MB */
119 #ifdef HAS_INCOHERENT_CACHES
120 static void force_mb_single_thread(struct reader_registry
*index
)
124 * pthread_kill has a smp_mb(). But beware, we assume it performs
125 * a cache flush on architectures with non-coherent cache. Let's play
126 * safe and don't assume anything : we use smp_mc() to make sure the
127 * cache flush is enforced.
130 smp_mc(); /* write ->need_mb before sending the signals */
131 pthread_kill(index
->tid
, SIGURCU
);
134 * Wait for sighandler (and thus mb()) to execute on every thread.
137 while (*index
->need_mb
) {
140 smp_mb(); /* read ->need_mb before ending the barrier */
142 #endif /* #ifdef HAS_INCOHERENT_CACHES */
144 static void force_mb_all_threads(void)
146 struct reader_registry
*index
;
148 * Ask for each threads to execute a smp_mb() so we can consider the
149 * compiler barriers around rcu read lock as real memory barriers.
154 * pthread_kill has a smp_mb(). But beware, we assume it performs
155 * a cache flush on architectures with non-coherent cache. Let's play
156 * safe and don't assume anything : we use smp_mc() to make sure the
157 * cache flush is enforced.
159 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
161 smp_mc(); /* write need_mb before sending the signal */
162 pthread_kill(index
->tid
, SIGURCU
);
165 * Wait for sighandler (and thus mb()) to execute on every thread.
167 * Note that the pthread_kill() will never be executed on systems
168 * that correctly deliver signals in a timely manner. However, it
169 * is not uncommon for kernels to have bugs that can result in
170 * lost or unduly delayed signals.
172 * If you are seeing the below pthread_kill() executing much at
173 * all, we suggest testing the underlying kernel and filing the
174 * relevant bug report. For Linux kernels, we recommend getting
175 * the Linux Test Project (LTP).
177 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
178 while (*index
->need_mb
) {
179 pthread_kill(index
->tid
, SIGURCU
);
183 smp_mb(); /* read ->need_mb before ending the barrier */
185 #endif /* #else #ifdef DEBUG_FULL_MB */
187 void wait_for_quiescent_state(void)
189 struct reader_registry
*index
;
194 * Wait for each thread urcu_active_readers count to become 0.
196 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
197 #ifndef HAS_INCOHERENT_CACHES
198 while (rcu_old_gp_ongoing(index
->urcu_active_readers
))
200 #else /* #ifndef HAS_INCOHERENT_CACHES */
203 * BUSY-LOOP. Force the reader thread to commit its
204 * urcu_active_readers update to memory if we wait for too long.
206 while (rcu_old_gp_ongoing(index
->urcu_active_readers
)) {
207 if (wait_loops
++ == KICK_READER_LOOPS
) {
208 force_mb_single_thread(index
);
214 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
218 void synchronize_rcu(void)
220 internal_urcu_lock();
222 /* All threads should read qparity before accessing data structure
223 * where new ptr points to. Must be done within internal_urcu_lock
224 * because it iterates on reader threads.*/
225 /* Write new ptr before changing the qparity */
226 force_mb_all_threads();
228 switch_next_urcu_qparity(); /* 0 -> 1 */
231 * Must commit qparity update to memory before waiting for parity
232 * 0 quiescent state. Failure to do so could result in the writer
233 * waiting forever while new readers are always accessing data (no
235 * Ensured by STORE_SHARED and LOAD_SHARED.
239 * Wait for previous parity to be empty of readers.
241 wait_for_quiescent_state(); /* Wait readers in parity 0 */
244 * Must finish waiting for quiescent state for parity 0 before
245 * committing qparity update to memory. Failure to do so could result in
246 * the writer waiting forever while new readers are always accessing
247 * data (no progress).
248 * Ensured by STORE_SHARED and LOAD_SHARED.
251 switch_next_urcu_qparity(); /* 1 -> 0 */
254 * Must commit qparity update to memory before waiting for parity
255 * 1 quiescent state. Failure to do so could result in the writer
256 * waiting forever while new readers are always accessing data (no
258 * Ensured by STORE_SHARED and LOAD_SHARED.
262 * Wait for previous parity to be empty of readers.
264 wait_for_quiescent_state(); /* Wait readers in parity 1 */
266 /* Finish waiting for reader threads before letting the old ptr being
267 * freed. Must be done within internal_urcu_lock because it iterates on
269 force_mb_all_threads();
271 internal_urcu_unlock();
275 * library wrappers to be used by non-LGPL compatible source code.
278 void rcu_read_lock(void)
283 void rcu_read_unlock(void)
288 void *rcu_dereference(void *p
)
290 return _rcu_dereference(p
);
293 void *rcu_assign_pointer_sym(void **p
, void *v
)
296 return STORE_SHARED(p
, v
);
299 void *rcu_xchg_pointer_sym(void **p
, void *v
)
305 void *rcu_publish_content_sym(void **p
, void *v
)
309 oldptr
= _rcu_xchg_pointer(p
, v
);
314 static void rcu_add_reader(pthread_t id
)
316 struct reader_registry
*oldarray
;
319 alloc_readers
= INIT_NUM_THREADS
;
322 malloc(sizeof(struct reader_registry
) * alloc_readers
);
324 if (alloc_readers
< num_readers
+ 1) {
326 registry
= malloc(sizeof(struct reader_registry
)
327 * (alloc_readers
<< 1));
328 memcpy(registry
, oldarray
,
329 sizeof(struct reader_registry
) * alloc_readers
);
333 registry
[num_readers
].tid
= id
;
334 /* reference to the TLS of _this_ reader thread. */
335 registry
[num_readers
].urcu_active_readers
= &urcu_active_readers
;
336 registry
[num_readers
].need_mb
= &need_mb
;
341 * Never shrink (implementation limitation).
342 * This is O(nb threads). Eventually use a hash table.
344 static void rcu_remove_reader(pthread_t id
)
346 struct reader_registry
*index
;
348 assert(registry
!= NULL
);
349 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
350 if (pthread_equal(index
->tid
, id
)) {
351 memcpy(index
, ®istry
[num_readers
- 1],
352 sizeof(struct reader_registry
));
353 registry
[num_readers
- 1].tid
= 0;
354 registry
[num_readers
- 1].urcu_active_readers
= NULL
;
359 /* Hrm not found, forgot to register ? */
363 void rcu_register_thread(void)
365 internal_urcu_lock();
366 rcu_add_reader(pthread_self());
367 internal_urcu_unlock();
370 void rcu_unregister_thread(void)
372 internal_urcu_lock();
373 rcu_remove_reader(pthread_self());
374 internal_urcu_unlock();
377 #ifndef DEBUG_FULL_MB
378 static void sigurcu_handler(int signo
, siginfo_t
*siginfo
, void *context
)
381 * Executing this smp_mb() is the only purpose of this signal handler.
382 * It punctually promotes barrier() into smp_mb() on every thread it is
390 void __attribute__((constructor
)) urcu_init(void)
392 struct sigaction act
;
395 act
.sa_sigaction
= sigurcu_handler
;
396 ret
= sigaction(SIGURCU
, &act
, NULL
);
398 perror("Error in sigaction");
403 void __attribute__((destructor
)) urcu_exit(void)
405 struct sigaction act
;
408 ret
= sigaction(SIGURCU
, NULL
, &act
);
410 perror("Error in sigaction");
413 assert(act
.sa_sigaction
== sigurcu_handler
);
416 #endif /* #ifndef DEBUG_FULL_MB */