4 * Userspace RCU library
6 * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
8 * Distributed under GPLv2
22 pthread_mutex_t urcu_mutex
= PTHREAD_MUTEX_INITIALIZER
;
25 * Global grace period counter.
26 * Contains the current RCU_GP_CTR_BIT.
27 * Also has a RCU_GP_CTR_BIT of 1, to accelerate the reader fast path.
28 * Written to only by writer with mutex taken. Read by both writer and readers.
30 long urcu_gp_ctr
= RCU_GP_COUNT
;
33 * Written to only by each individual reader. Read by both the reader and the
36 long __thread urcu_active_readers
;
38 /* Thread IDs of registered readers */
39 #define INIT_NUM_THREADS 4
41 struct reader_registry
{
43 long *urcu_active_readers
;
48 unsigned int yield_active
;
49 unsigned int __thread rand_yield
;
52 static struct reader_registry
*registry
;
53 static char __thread need_mb
;
54 static int num_readers
, alloc_readers
;
56 void internal_urcu_lock(void)
60 #ifndef DISTRUST_SIGNALS_EXTREME
61 ret
= pthread_mutex_lock(&urcu_mutex
);
63 perror("Error in pthread mutex lock");
66 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
67 while ((ret
= pthread_mutex_trylock(&urcu_mutex
)) != 0) {
68 if (ret
!= EBUSY
&& ret
!= EINTR
) {
69 printf("ret = %d, errno = %d\n", ret
, errno
);
70 perror("Error in pthread mutex lock");
80 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
83 void internal_urcu_unlock(void)
87 ret
= pthread_mutex_unlock(&urcu_mutex
);
89 perror("Error in pthread mutex unlock");
95 * called with urcu_mutex held.
97 static void switch_next_urcu_qparity(void)
99 STORE_SHARED(urcu_gp_ctr
, urcu_gp_ctr
^ RCU_GP_CTR_BIT
);
103 #ifdef HAS_INCOHERENT_CACHES
104 static void force_mb_single_thread(struct reader_registry
*index
)
108 #endif /* #ifdef HAS_INCOHERENT_CACHES */
110 static void force_mb_all_threads(void)
114 #else /* #ifdef DEBUG_FULL_MB */
115 #ifdef HAS_INCOHERENT_CACHES
116 static void force_mb_single_thread(struct reader_registry
*index
)
120 * pthread_kill has a smp_mb(). But beware, we assume it performs
121 * a cache flush on architectures with non-coherent cache. Let's play
122 * safe and don't assume anything : we use smp_mc() to make sure the
123 * cache flush is enforced.
126 smp_mc(); /* write ->need_mb before sending the signals */
127 pthread_kill(index
->tid
, SIGURCU
);
130 * Wait for sighandler (and thus mb()) to execute on every thread.
133 while (*index
->need_mb
) {
136 smp_mb(); /* read ->need_mb before ending the barrier */
138 #endif /* #ifdef HAS_INCOHERENT_CACHES */
140 static void force_mb_all_threads(void)
142 struct reader_registry
*index
;
144 * Ask for each threads to execute a smp_mb() so we can consider the
145 * compiler barriers around rcu read lock as real memory barriers.
150 * pthread_kill has a smp_mb(). But beware, we assume it performs
151 * a cache flush on architectures with non-coherent cache. Let's play
152 * safe and don't assume anything : we use smp_mc() to make sure the
153 * cache flush is enforced.
155 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
157 smp_mc(); /* write need_mb before sending the signal */
158 pthread_kill(index
->tid
, SIGURCU
);
161 * Wait for sighandler (and thus mb()) to execute on every thread.
163 * Note that the pthread_kill() will never be executed on systems
164 * that correctly deliver signals in a timely manner. However, it
165 * is not uncommon for kernels to have bugs that can result in
166 * lost or unduly delayed signals.
168 * If you are seeing the below pthread_kill() executing much at
169 * all, we suggest testing the underlying kernel and filing the
170 * relevant bug report. For Linux kernels, we recommend getting
171 * the Linux Test Project (LTP).
173 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
174 while (*index
->need_mb
) {
175 pthread_kill(index
->tid
, SIGURCU
);
179 smp_mb(); /* read ->need_mb before ending the barrier */
181 #endif /* #else #ifdef DEBUG_FULL_MB */
183 void wait_for_quiescent_state(void)
185 struct reader_registry
*index
;
190 * Wait for each thread urcu_active_readers count to become 0.
192 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
193 #ifndef HAS_INCOHERENT_CACHES
194 while (rcu_old_gp_ongoing(index
->urcu_active_readers
))
196 #else /* #ifndef HAS_INCOHERENT_CACHES */
199 * BUSY-LOOP. Force the reader thread to commit its
200 * urcu_active_readers update to memory if we wait for too long.
202 while (rcu_old_gp_ongoing(index
->urcu_active_readers
)) {
203 if (wait_loops
++ == KICK_READER_LOOPS
) {
204 force_mb_single_thread(index
);
210 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
214 void synchronize_rcu(void)
216 internal_urcu_lock();
218 /* All threads should read qparity before accessing data structure
219 * where new ptr points to. Must be done within internal_urcu_lock
220 * because it iterates on reader threads.*/
221 /* Write new ptr before changing the qparity */
222 force_mb_all_threads();
224 switch_next_urcu_qparity(); /* 0 -> 1 */
227 * Must commit qparity update to memory before waiting for parity
228 * 0 quiescent state. Failure to do so could result in the writer
229 * waiting forever while new readers are always accessing data (no
231 * Ensured by STORE_SHARED and LOAD_SHARED.
235 * Wait for previous parity to be empty of readers.
237 wait_for_quiescent_state(); /* Wait readers in parity 0 */
240 * Must finish waiting for quiescent state for parity 0 before
241 * committing qparity update to memory. Failure to do so could result in
242 * the writer waiting forever while new readers are always accessing
243 * data (no progress).
244 * Ensured by STORE_SHARED and LOAD_SHARED.
247 switch_next_urcu_qparity(); /* 1 -> 0 */
250 * Must commit qparity update to memory before waiting for parity
251 * 1 quiescent state. Failure to do so could result in the writer
252 * waiting forever while new readers are always accessing data (no
254 * Ensured by STORE_SHARED and LOAD_SHARED.
258 * Wait for previous parity to be empty of readers.
260 wait_for_quiescent_state(); /* Wait readers in parity 1 */
262 /* Finish waiting for reader threads before letting the old ptr being
263 * freed. Must be done within internal_urcu_lock because it iterates on
265 force_mb_all_threads();
267 internal_urcu_unlock();
270 void urcu_add_reader(pthread_t id
)
272 struct reader_registry
*oldarray
;
275 alloc_readers
= INIT_NUM_THREADS
;
278 malloc(sizeof(struct reader_registry
) * alloc_readers
);
280 if (alloc_readers
< num_readers
+ 1) {
282 registry
= malloc(sizeof(struct reader_registry
)
283 * (alloc_readers
<< 1));
284 memcpy(registry
, oldarray
,
285 sizeof(struct reader_registry
) * alloc_readers
);
289 registry
[num_readers
].tid
= id
;
290 /* reference to the TLS of _this_ reader thread. */
291 registry
[num_readers
].urcu_active_readers
= &urcu_active_readers
;
292 registry
[num_readers
].need_mb
= &need_mb
;
297 * Never shrink (implementation limitation).
298 * This is O(nb threads). Eventually use a hash table.
300 void urcu_remove_reader(pthread_t id
)
302 struct reader_registry
*index
;
304 assert(registry
!= NULL
);
305 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
306 if (pthread_equal(index
->tid
, id
)) {
307 memcpy(index
, ®istry
[num_readers
- 1],
308 sizeof(struct reader_registry
));
309 registry
[num_readers
- 1].tid
= 0;
310 registry
[num_readers
- 1].urcu_active_readers
= NULL
;
315 /* Hrm not found, forgot to register ? */
319 void urcu_register_thread(void)
321 internal_urcu_lock();
322 urcu_add_reader(pthread_self());
323 internal_urcu_unlock();
326 void urcu_unregister_thread(void)
328 internal_urcu_lock();
329 urcu_remove_reader(pthread_self());
330 internal_urcu_unlock();
333 #ifndef DEBUG_FULL_MB
334 void sigurcu_handler(int signo
, siginfo_t
*siginfo
, void *context
)
337 * Executing this smp_mb() is the only purpose of this signal handler.
338 * It punctually promotes barrier() into smp_mb() on every thread it is
346 void __attribute__((constructor
)) urcu_init(void)
348 struct sigaction act
;
351 act
.sa_sigaction
= sigurcu_handler
;
352 ret
= sigaction(SIGURCU
, &act
, NULL
);
354 perror("Error in sigaction");
359 void __attribute__((destructor
)) urcu_exit(void)
361 struct sigaction act
;
364 ret
= sigaction(SIGURCU
, NULL
, &act
);
366 perror("Error in sigaction");
369 assert(act
.sa_sigaction
== sigurcu_handler
);
372 #endif /* #ifndef DEBUG_FULL_MB */