Remove rep_nop() (GPL)
[urcu.git] / urcu.c
1 /*
2 * urcu.c
3 *
4 * Userspace RCU library
5 *
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
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 #include <stdio.h>
27 #include <pthread.h>
28 #include <signal.h>
29 #include <assert.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <errno.h>
33 #include <poll.h>
34
35 #include "urcu-static.h"
36 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
37 #include "urcu.h"
38
39 pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER;
40
41 /*
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.
46 */
47 long urcu_gp_ctr = RCU_GP_COUNT;
48
49 /*
50 * Written to only by each individual reader. Read by both the reader and the
51 * writers.
52 */
53 long __thread urcu_active_readers;
54
55 /* Thread IDs of registered readers */
56 #define INIT_NUM_THREADS 4
57
58 struct reader_registry {
59 pthread_t tid;
60 long *urcu_active_readers;
61 char *need_mb;
62 };
63
64 #ifdef DEBUG_YIELD
65 unsigned int yield_active;
66 unsigned int __thread rand_yield;
67 #endif
68
69 static struct reader_registry *registry;
70 static char __thread need_mb;
71 static int num_readers, alloc_readers;
72
73 void internal_urcu_lock(void)
74 {
75 int ret;
76
77 #ifndef DISTRUST_SIGNALS_EXTREME
78 ret = pthread_mutex_lock(&urcu_mutex);
79 if (ret) {
80 perror("Error in pthread mutex lock");
81 exit(-1);
82 }
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");
88 exit(-1);
89 }
90 if (need_mb) {
91 smp_mb();
92 need_mb = 0;
93 smp_mb();
94 }
95 poll(NULL,0,10);
96 }
97 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
98 }
99
100 void internal_urcu_unlock(void)
101 {
102 int ret;
103
104 ret = pthread_mutex_unlock(&urcu_mutex);
105 if (ret) {
106 perror("Error in pthread mutex unlock");
107 exit(-1);
108 }
109 }
110
111 /*
112 * called with urcu_mutex held.
113 */
114 static void switch_next_urcu_qparity(void)
115 {
116 STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr ^ RCU_GP_CTR_BIT);
117 }
118
119 #ifdef DEBUG_FULL_MB
120 #ifdef HAS_INCOHERENT_CACHES
121 static void force_mb_single_thread(struct reader_registry *index)
122 {
123 smp_mb();
124 }
125 #endif /* #ifdef HAS_INCOHERENT_CACHES */
126
127 static void force_mb_all_threads(void)
128 {
129 smp_mb();
130 }
131 #else /* #ifdef DEBUG_FULL_MB */
132 #ifdef HAS_INCOHERENT_CACHES
133 static void force_mb_single_thread(struct reader_registry *index)
134 {
135 assert(registry);
136 /*
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.
141 */
142 *index->need_mb = 1;
143 smp_mc(); /* write ->need_mb before sending the signals */
144 pthread_kill(index->tid, SIGURCU);
145 smp_mb();
146 /*
147 * Wait for sighandler (and thus mb()) to execute on every thread.
148 * BUSY-LOOP.
149 */
150 while (*index->need_mb) {
151 poll(NULL, 0, 1);
152 }
153 smp_mb(); /* read ->need_mb before ending the barrier */
154 }
155 #endif /* #ifdef HAS_INCOHERENT_CACHES */
156
157 static void force_mb_all_threads(void)
158 {
159 struct reader_registry *index;
160 /*
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.
163 */
164 if (!registry)
165 return;
166 /*
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.
171 */
172 for (index = registry; index < registry + num_readers; index++) {
173 *index->need_mb = 1;
174 smp_mc(); /* write need_mb before sending the signal */
175 pthread_kill(index->tid, SIGURCU);
176 }
177 /*
178 * Wait for sighandler (and thus mb()) to execute on every thread.
179 *
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.
184 *
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).
189 */
190 for (index = registry; index < registry + num_readers; index++) {
191 while (*index->need_mb) {
192 pthread_kill(index->tid, SIGURCU);
193 poll(NULL, 0, 1);
194 }
195 }
196 smp_mb(); /* read ->need_mb before ending the barrier */
197 }
198 #endif /* #else #ifdef DEBUG_FULL_MB */
199
200 void wait_for_quiescent_state(void)
201 {
202 struct reader_registry *index;
203
204 if (!registry)
205 return;
206 /*
207 * Wait for each thread urcu_active_readers count to become 0.
208 */
209 for (index = registry; index < registry + num_readers; index++) {
210 #ifndef HAS_INCOHERENT_CACHES
211 while (rcu_old_gp_ongoing(index->urcu_active_readers))
212 cpu_relax();
213 #else /* #ifndef HAS_INCOHERENT_CACHES */
214 int wait_loops = 0;
215 /*
216 * BUSY-LOOP. Force the reader thread to commit its
217 * urcu_active_readers update to memory if we wait for too long.
218 */
219 while (rcu_old_gp_ongoing(index->urcu_active_readers)) {
220 if (wait_loops++ == KICK_READER_LOOPS) {
221 force_mb_single_thread(index);
222 wait_loops = 0;
223 } else {
224 cpu_relax();
225 }
226 }
227 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
228 }
229 }
230
231 void synchronize_rcu(void)
232 {
233 internal_urcu_lock();
234
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();
240
241 switch_next_urcu_qparity(); /* 0 -> 1 */
242
243 /*
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
247 * progress).
248 * Ensured by STORE_SHARED and LOAD_SHARED.
249 */
250
251 /*
252 * Wait for previous parity to be empty of readers.
253 */
254 wait_for_quiescent_state(); /* Wait readers in parity 0 */
255
256 /*
257 * Must finish waiting for quiescent state for parity 0 before
258 * committing qparity update to memory. Failure to do so could result in
259 * the writer waiting forever while new readers are always accessing
260 * data (no progress).
261 * Ensured by STORE_SHARED and LOAD_SHARED.
262 */
263
264 switch_next_urcu_qparity(); /* 1 -> 0 */
265
266 /*
267 * Must commit qparity update to memory before waiting for parity
268 * 1 quiescent state. Failure to do so could result in the writer
269 * waiting forever while new readers are always accessing data (no
270 * progress).
271 * Ensured by STORE_SHARED and LOAD_SHARED.
272 */
273
274 /*
275 * Wait for previous parity to be empty of readers.
276 */
277 wait_for_quiescent_state(); /* Wait readers in parity 1 */
278
279 /* Finish waiting for reader threads before letting the old ptr being
280 * freed. Must be done within internal_urcu_lock because it iterates on
281 * reader threads. */
282 force_mb_all_threads();
283
284 internal_urcu_unlock();
285 }
286
287 /*
288 * library wrappers to be used by non-LGPL compatible source code.
289 */
290
291 void rcu_read_lock(void)
292 {
293 _rcu_read_lock();
294 }
295
296 void rcu_read_unlock(void)
297 {
298 _rcu_read_unlock();
299 }
300
301 void *rcu_dereference(void *p)
302 {
303 return _rcu_dereference(p);
304 }
305
306 void *rcu_assign_pointer_sym(void **p, void *v)
307 {
308 wmb();
309 return STORE_SHARED(p, v);
310 }
311
312 void *rcu_xchg_pointer_sym(void **p, void *v)
313 {
314 wmb();
315 return xchg(p, v);
316 }
317
318 void *rcu_publish_content_sym(void **p, void *v)
319 {
320 void *oldptr;
321
322 oldptr = _rcu_xchg_pointer(p, v);
323 synchronize_rcu();
324 return oldptr;
325 }
326
327 static void rcu_add_reader(pthread_t id)
328 {
329 struct reader_registry *oldarray;
330
331 if (!registry) {
332 alloc_readers = INIT_NUM_THREADS;
333 num_readers = 0;
334 registry =
335 malloc(sizeof(struct reader_registry) * alloc_readers);
336 }
337 if (alloc_readers < num_readers + 1) {
338 oldarray = registry;
339 registry = malloc(sizeof(struct reader_registry)
340 * (alloc_readers << 1));
341 memcpy(registry, oldarray,
342 sizeof(struct reader_registry) * alloc_readers);
343 alloc_readers <<= 1;
344 free(oldarray);
345 }
346 registry[num_readers].tid = id;
347 /* reference to the TLS of _this_ reader thread. */
348 registry[num_readers].urcu_active_readers = &urcu_active_readers;
349 registry[num_readers].need_mb = &need_mb;
350 num_readers++;
351 }
352
353 /*
354 * Never shrink (implementation limitation).
355 * This is O(nb threads). Eventually use a hash table.
356 */
357 static void rcu_remove_reader(pthread_t id)
358 {
359 struct reader_registry *index;
360
361 assert(registry != NULL);
362 for (index = registry; index < registry + num_readers; index++) {
363 if (pthread_equal(index->tid, id)) {
364 memcpy(index, &registry[num_readers - 1],
365 sizeof(struct reader_registry));
366 registry[num_readers - 1].tid = 0;
367 registry[num_readers - 1].urcu_active_readers = NULL;
368 num_readers--;
369 return;
370 }
371 }
372 /* Hrm not found, forgot to register ? */
373 assert(0);
374 }
375
376 void rcu_register_thread(void)
377 {
378 internal_urcu_lock();
379 rcu_add_reader(pthread_self());
380 internal_urcu_unlock();
381 }
382
383 void rcu_unregister_thread(void)
384 {
385 internal_urcu_lock();
386 rcu_remove_reader(pthread_self());
387 internal_urcu_unlock();
388 }
389
390 #ifndef DEBUG_FULL_MB
391 static void sigurcu_handler(int signo, siginfo_t *siginfo, void *context)
392 {
393 /*
394 * Executing this smp_mb() is the only purpose of this signal handler.
395 * It punctually promotes barrier() into smp_mb() on every thread it is
396 * executed on.
397 */
398 smp_mb();
399 need_mb = 0;
400 smp_mb();
401 }
402
403 void __attribute__((constructor)) urcu_init(void)
404 {
405 struct sigaction act;
406 int ret;
407
408 act.sa_sigaction = sigurcu_handler;
409 ret = sigaction(SIGURCU, &act, NULL);
410 if (ret) {
411 perror("Error in sigaction");
412 exit(-1);
413 }
414 }
415
416 void __attribute__((destructor)) urcu_exit(void)
417 {
418 struct sigaction act;
419 int ret;
420
421 ret = sigaction(SIGURCU, NULL, &act);
422 if (ret) {
423 perror("Error in sigaction");
424 exit(-1);
425 }
426 assert(act.sa_sigaction == sigurcu_handler);
427 free(registry);
428 }
429 #endif /* #ifndef DEBUG_FULL_MB */
This page took 0.04891 seconds and 4 git commands to generate.