4 * Userspace RCU library
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
7 * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
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.
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.
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
23 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
35 #include "urcu-static.h"
36 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
39 pthread_mutex_t urcu_mutex
= PTHREAD_MUTEX_INITIALIZER
;
42 * Global grace period counter.
43 * Contains the current RCU_GP_CTR_BIT.
44 * Also has a RCU_GP_CTR_BIT of 1, to accelerate the reader fast path.
45 * Written to only by writer with mutex taken. Read by both writer and readers.
47 long urcu_gp_ctr
= RCU_GP_COUNT
;
50 * Written to only by each individual reader. Read by both the reader and the
53 long __thread urcu_active_readers
;
55 /* Thread IDs of registered readers */
56 #define INIT_NUM_THREADS 4
58 struct reader_registry
{
60 long *urcu_active_readers
;
65 unsigned int yield_active
;
66 unsigned int __thread rand_yield
;
69 static struct reader_registry
*registry
;
70 static char __thread need_mb
;
71 static int num_readers
, alloc_readers
;
73 void internal_urcu_lock(void)
77 #ifndef DISTRUST_SIGNALS_EXTREME
78 ret
= pthread_mutex_lock(&urcu_mutex
);
80 perror("Error in pthread mutex lock");
83 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
84 while ((ret
= pthread_mutex_trylock(&urcu_mutex
)) != 0) {
85 if (ret
!= EBUSY
&& ret
!= EINTR
) {
86 printf("ret = %d, errno = %d\n", ret
, errno
);
87 perror("Error in pthread mutex lock");
97 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
100 void internal_urcu_unlock(void)
104 ret
= pthread_mutex_unlock(&urcu_mutex
);
106 perror("Error in pthread mutex unlock");
112 * called with urcu_mutex held.
114 static void switch_next_urcu_qparity(void)
116 STORE_SHARED(urcu_gp_ctr
, urcu_gp_ctr
^ RCU_GP_CTR_BIT
);
120 #ifdef HAS_INCOHERENT_CACHES
121 static void force_mb_single_thread(struct reader_registry
*index
)
125 #endif /* #ifdef HAS_INCOHERENT_CACHES */
127 static void force_mb_all_threads(void)
131 #else /* #ifdef DEBUG_FULL_MB */
132 #ifdef HAS_INCOHERENT_CACHES
133 static void force_mb_single_thread(struct reader_registry
*index
)
137 * pthread_kill has a smp_mb(). But beware, we assume it performs
138 * a cache flush on architectures with non-coherent cache. Let's play
139 * safe and don't assume anything : we use smp_mc() to make sure the
140 * cache flush is enforced.
143 smp_mc(); /* write ->need_mb before sending the signals */
144 pthread_kill(index
->tid
, SIGURCU
);
147 * Wait for sighandler (and thus mb()) to execute on every thread.
150 while (*index
->need_mb
) {
153 smp_mb(); /* read ->need_mb before ending the barrier */
155 #endif /* #ifdef HAS_INCOHERENT_CACHES */
157 static void force_mb_all_threads(void)
159 struct reader_registry
*index
;
161 * Ask for each threads to execute a smp_mb() so we can consider the
162 * compiler barriers around rcu read lock as real memory barriers.
167 * pthread_kill has a smp_mb(). But beware, we assume it performs
168 * a cache flush on architectures with non-coherent cache. Let's play
169 * safe and don't assume anything : we use smp_mc() to make sure the
170 * cache flush is enforced.
172 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
174 smp_mc(); /* write need_mb before sending the signal */
175 pthread_kill(index
->tid
, SIGURCU
);
178 * Wait for sighandler (and thus mb()) to execute on every thread.
180 * Note that the pthread_kill() will never be executed on systems
181 * that correctly deliver signals in a timely manner. However, it
182 * is not uncommon for kernels to have bugs that can result in
183 * lost or unduly delayed signals.
185 * If you are seeing the below pthread_kill() executing much at
186 * all, we suggest testing the underlying kernel and filing the
187 * relevant bug report. For Linux kernels, we recommend getting
188 * the Linux Test Project (LTP).
190 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
191 while (*index
->need_mb
) {
192 pthread_kill(index
->tid
, SIGURCU
);
196 smp_mb(); /* read ->need_mb before ending the barrier */
198 #endif /* #else #ifdef DEBUG_FULL_MB */
200 void wait_for_quiescent_state(void)
202 struct reader_registry
*index
;
207 * Wait for each thread urcu_active_readers count to become 0.
209 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
210 #ifndef HAS_INCOHERENT_CACHES
211 while (rcu_old_gp_ongoing(index
->urcu_active_readers
))
213 #else /* #ifndef HAS_INCOHERENT_CACHES */
216 * BUSY-LOOP. Force the reader thread to commit its
217 * urcu_active_readers update to memory if we wait for too long.
219 while (rcu_old_gp_ongoing(index
->urcu_active_readers
)) {
220 if (wait_loops
++ == KICK_READER_LOOPS
) {
221 force_mb_single_thread(index
);
227 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
231 void synchronize_rcu(void)
233 internal_urcu_lock();
235 /* All threads should read qparity before accessing data structure
236 * where new ptr points to. Must be done within internal_urcu_lock
237 * because it iterates on reader threads.*/
238 /* Write new ptr before changing the qparity */
239 force_mb_all_threads();
241 switch_next_urcu_qparity(); /* 0 -> 1 */
244 * Must commit qparity update to memory before waiting for parity
245 * 0 quiescent state. Failure to do so could result in the writer
246 * waiting forever while new readers are always accessing data (no
248 * Ensured by STORE_SHARED and LOAD_SHARED.
252 * Current RCU formal verification model assumes sequential execution of
253 * the write-side. Add core synchronization instructions. Can be removed
254 * if the formal model is extended to prove that reordering is still
257 sync_core(); /* Formal model assumes serialized execution */
260 * Wait for previous parity to be empty of readers.
262 wait_for_quiescent_state(); /* Wait readers in parity 0 */
265 * Must finish waiting for quiescent state for parity 0 before
266 * committing qparity update to memory. Failure to do so could result in
267 * the writer waiting forever while new readers are always accessing
268 * data (no progress).
269 * Ensured by STORE_SHARED and LOAD_SHARED.
272 sync_core(); /* Formal model assumes serialized execution */
274 switch_next_urcu_qparity(); /* 1 -> 0 */
277 * Must commit qparity update to memory before waiting for parity
278 * 1 quiescent state. Failure to do so could result in the writer
279 * waiting forever while new readers are always accessing data (no
281 * Ensured by STORE_SHARED and LOAD_SHARED.
284 sync_core(); /* Formal model assumes serialized execution */
287 * Wait for previous parity to be empty of readers.
289 wait_for_quiescent_state(); /* Wait readers in parity 1 */
291 /* Finish waiting for reader threads before letting the old ptr being
292 * freed. Must be done within internal_urcu_lock because it iterates on
294 force_mb_all_threads();
296 internal_urcu_unlock();
300 * library wrappers to be used by non-LGPL compatible source code.
303 void rcu_read_lock(void)
308 void rcu_read_unlock(void)
313 void *rcu_dereference(void *p
)
315 return _rcu_dereference(p
);
318 void *rcu_assign_pointer_sym(void **p
, void *v
)
321 return STORE_SHARED(p
, v
);
324 void *rcu_xchg_pointer_sym(void **p
, void *v
)
330 void *rcu_publish_content_sym(void **p
, void *v
)
334 oldptr
= _rcu_xchg_pointer(p
, v
);
339 static void rcu_add_reader(pthread_t id
)
341 struct reader_registry
*oldarray
;
344 alloc_readers
= INIT_NUM_THREADS
;
347 malloc(sizeof(struct reader_registry
) * alloc_readers
);
349 if (alloc_readers
< num_readers
+ 1) {
351 registry
= malloc(sizeof(struct reader_registry
)
352 * (alloc_readers
<< 1));
353 memcpy(registry
, oldarray
,
354 sizeof(struct reader_registry
) * alloc_readers
);
358 registry
[num_readers
].tid
= id
;
359 /* reference to the TLS of _this_ reader thread. */
360 registry
[num_readers
].urcu_active_readers
= &urcu_active_readers
;
361 registry
[num_readers
].need_mb
= &need_mb
;
366 * Never shrink (implementation limitation).
367 * This is O(nb threads). Eventually use a hash table.
369 static void rcu_remove_reader(pthread_t id
)
371 struct reader_registry
*index
;
373 assert(registry
!= NULL
);
374 for (index
= registry
; index
< registry
+ num_readers
; index
++) {
375 if (pthread_equal(index
->tid
, id
)) {
376 memcpy(index
, ®istry
[num_readers
- 1],
377 sizeof(struct reader_registry
));
378 registry
[num_readers
- 1].tid
= 0;
379 registry
[num_readers
- 1].urcu_active_readers
= NULL
;
384 /* Hrm not found, forgot to register ? */
388 void rcu_register_thread(void)
390 internal_urcu_lock();
391 rcu_add_reader(pthread_self());
392 internal_urcu_unlock();
395 void rcu_unregister_thread(void)
397 internal_urcu_lock();
398 rcu_remove_reader(pthread_self());
399 internal_urcu_unlock();
402 #ifndef DEBUG_FULL_MB
403 static void sigurcu_handler(int signo
, siginfo_t
*siginfo
, void *context
)
406 * Executing this smp_mb() is the only purpose of this signal handler.
407 * It punctually promotes barrier() into smp_mb() on every thread it is
415 void __attribute__((constructor
)) urcu_init(void)
417 struct sigaction act
;
420 act
.sa_sigaction
= sigurcu_handler
;
421 ret
= sigaction(SIGURCU
, &act
, NULL
);
423 perror("Error in sigaction");
428 void __attribute__((destructor
)) urcu_exit(void)
430 struct sigaction act
;
433 ret
= sigaction(SIGURCU
, NULL
, &act
);
435 perror("Error in sigaction");
438 assert(act
.sa_sigaction
== sigurcu_handler
);
441 #endif /* #ifndef DEBUG_FULL_MB */