Check for __linux__ before including syscall.h
[urcu.git] / urcu.c
1 /*
2 * urcu.c
3 *
4 * Userspace RCU library
5 *
6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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 #define _BSD_SOURCE
27 #define _GNU_SOURCE
28 #include <stdio.h>
29 #include <pthread.h>
30 #include <signal.h>
31 #include <assert.h>
32 #include <stdlib.h>
33 #include <stdint.h>
34 #include <string.h>
35 #include <errno.h>
36 #include <poll.h>
37
38 #include "urcu/map/urcu.h"
39
40 #include "urcu/static/urcu.h"
41 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
42 #include "urcu.h"
43
44 #ifdef RCU_MEMBARRIER
45 static int init_done;
46 int has_sys_membarrier;
47
48 void __attribute__((constructor)) rcu_init(void);
49 #endif
50
51 #ifdef RCU_MB
52 void rcu_init(void)
53 {
54 }
55 #endif
56
57 #ifdef RCU_SIGNAL
58 static int init_done;
59
60 void __attribute__((constructor)) rcu_init(void);
61 void __attribute__((destructor)) rcu_exit(void);
62 #endif
63
64 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
65
66 int32_t gp_futex;
67
68 /*
69 * Global grace period counter.
70 * Contains the current RCU_GP_CTR_PHASE.
71 * Also has a RCU_GP_COUNT of 1, to accelerate the reader fast path.
72 * Written to only by writer with mutex taken. Read by both writer and readers.
73 */
74 unsigned long rcu_gp_ctr = RCU_GP_COUNT;
75
76 /*
77 * Written to only by each individual reader. Read by both the reader and the
78 * writers.
79 */
80 struct rcu_reader __thread rcu_reader;
81
82 #ifdef DEBUG_YIELD
83 unsigned int yield_active;
84 unsigned int __thread rand_yield;
85 #endif
86
87 static CDS_LIST_HEAD(registry);
88
89 static void mutex_lock(pthread_mutex_t *mutex)
90 {
91 int ret;
92
93 #ifndef DISTRUST_SIGNALS_EXTREME
94 ret = pthread_mutex_lock(mutex);
95 if (ret) {
96 perror("Error in pthread mutex lock");
97 exit(-1);
98 }
99 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
100 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
101 if (ret != EBUSY && ret != EINTR) {
102 printf("ret = %d, errno = %d\n", ret, errno);
103 perror("Error in pthread mutex lock");
104 exit(-1);
105 }
106 if (CMM_LOAD_SHARED(rcu_reader.need_mb)) {
107 cmm_smp_mb();
108 _CMM_STORE_SHARED(rcu_reader.need_mb, 0);
109 cmm_smp_mb();
110 }
111 poll(NULL,0,10);
112 }
113 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
114 }
115
116 static void mutex_unlock(pthread_mutex_t *mutex)
117 {
118 int ret;
119
120 ret = pthread_mutex_unlock(mutex);
121 if (ret) {
122 perror("Error in pthread mutex unlock");
123 exit(-1);
124 }
125 }
126
127 #ifdef RCU_MEMBARRIER
128 static void smp_mb_master(int group)
129 {
130 if (likely(has_sys_membarrier))
131 membarrier(MEMBARRIER_EXPEDITED);
132 else
133 cmm_smp_mb();
134 }
135 #endif
136
137 #ifdef RCU_MB
138 static void smp_mb_master(int group)
139 {
140 cmm_smp_mb();
141 }
142 #endif
143
144 #ifdef RCU_SIGNAL
145 static void force_mb_all_readers(void)
146 {
147 struct rcu_reader *index;
148
149 /*
150 * Ask for each threads to execute a cmm_smp_mb() so we can consider the
151 * compiler barriers around rcu read lock as real memory barriers.
152 */
153 if (cds_list_empty(&registry))
154 return;
155 /*
156 * pthread_kill has a cmm_smp_mb(). But beware, we assume it performs
157 * a cache flush on architectures with non-coherent cache. Let's play
158 * safe and don't assume anything : we use cmm_smp_mc() to make sure the
159 * cache flush is enforced.
160 */
161 cds_list_for_each_entry(index, &registry, node) {
162 CMM_STORE_SHARED(index->need_mb, 1);
163 pthread_kill(index->tid, SIGRCU);
164 }
165 /*
166 * Wait for sighandler (and thus mb()) to execute on every thread.
167 *
168 * Note that the pthread_kill() will never be executed on systems
169 * that correctly deliver signals in a timely manner. However, it
170 * is not uncommon for kernels to have bugs that can result in
171 * lost or unduly delayed signals.
172 *
173 * If you are seeing the below pthread_kill() executing much at
174 * all, we suggest testing the underlying kernel and filing the
175 * relevant bug report. For Linux kernels, we recommend getting
176 * the Linux Test Project (LTP).
177 */
178 cds_list_for_each_entry(index, &registry, node) {
179 while (CMM_LOAD_SHARED(index->need_mb)) {
180 pthread_kill(index->tid, SIGRCU);
181 poll(NULL, 0, 1);
182 }
183 }
184 cmm_smp_mb(); /* read ->need_mb before ending the barrier */
185 }
186
187 static void smp_mb_master(int group)
188 {
189 force_mb_all_readers();
190 }
191 #endif /* #ifdef RCU_SIGNAL */
192
193 /*
194 * synchronize_rcu() waiting. Single thread.
195 */
196 static void wait_gp(void)
197 {
198 /* Read reader_gp before read futex */
199 smp_mb_master(RCU_MB_GROUP);
200 if (uatomic_read(&gp_futex) == -1)
201 futex_async(&gp_futex, FUTEX_WAIT, -1,
202 NULL, NULL, 0);
203 }
204
205 void update_counter_and_wait(void)
206 {
207 CDS_LIST_HEAD(qsreaders);
208 int wait_loops = 0;
209 struct rcu_reader *index, *tmp;
210
211 /* Switch parity: 0 -> 1, 1 -> 0 */
212 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
213
214 /*
215 * Must commit rcu_gp_ctr update to memory before waiting for quiescent
216 * state. Failure to do so could result in the writer waiting forever
217 * while new readers are always accessing data (no progress). Enforce
218 * compiler-order of store to rcu_gp_ctr before load rcu_reader ctr.
219 */
220 cmm_barrier();
221
222 /*
223 *
224 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
225 * model easier to understand. It does not have a big performance impact
226 * anyway, given this is the write-side.
227 */
228 cmm_smp_mb();
229
230 /*
231 * Wait for each thread rcu_reader.ctr count to become 0.
232 */
233 for (;;) {
234 wait_loops++;
235 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
236 uatomic_dec(&gp_futex);
237 /* Write futex before read reader_gp */
238 smp_mb_master(RCU_MB_GROUP);
239 }
240
241 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
242 if (!rcu_gp_ongoing(&index->ctr))
243 cds_list_move(&index->node, &qsreaders);
244 }
245
246 #ifndef HAS_INCOHERENT_CACHES
247 if (cds_list_empty(&registry)) {
248 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
249 /* Read reader_gp before write futex */
250 smp_mb_master(RCU_MB_GROUP);
251 uatomic_set(&gp_futex, 0);
252 }
253 break;
254 } else {
255 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
256 wait_gp();
257 else
258 caa_cpu_relax();
259 }
260 #else /* #ifndef HAS_INCOHERENT_CACHES */
261 /*
262 * BUSY-LOOP. Force the reader thread to commit its
263 * rcu_reader.ctr update to memory if we wait for too long.
264 */
265 if (cds_list_empty(&registry)) {
266 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS) {
267 /* Read reader_gp before write futex */
268 smp_mb_master(RCU_MB_GROUP);
269 uatomic_set(&gp_futex, 0);
270 }
271 break;
272 } else {
273 switch (wait_loops) {
274 case RCU_QS_ACTIVE_ATTEMPTS:
275 wait_gp();
276 break; /* only escape switch */
277 case KICK_READER_LOOPS:
278 smp_mb_master(RCU_MB_GROUP);
279 wait_loops = 0;
280 break; /* only escape switch */
281 default:
282 caa_cpu_relax();
283 }
284 }
285 #endif /* #else #ifndef HAS_INCOHERENT_CACHES */
286 }
287 /* put back the reader list in the registry */
288 cds_list_splice(&qsreaders, &registry);
289 }
290
291 void synchronize_rcu(void)
292 {
293 mutex_lock(&rcu_gp_lock);
294
295 if (cds_list_empty(&registry))
296 goto out;
297
298 /* All threads should read qparity before accessing data structure
299 * where new ptr points to. Must be done within rcu_gp_lock because it
300 * iterates on reader threads.*/
301 /* Write new ptr before changing the qparity */
302 smp_mb_master(RCU_MB_GROUP);
303
304 /*
305 * Wait for previous parity to be empty of readers.
306 */
307 update_counter_and_wait(); /* 0 -> 1, wait readers in parity 0 */
308
309 /*
310 * Must finish waiting for quiescent state for parity 0 before
311 * committing next rcu_gp_ctr update to memory. Failure to do so could
312 * result in the writer waiting forever while new readers are always
313 * accessing data (no progress). Enforce compiler-order of load
314 * rcu_reader ctr before store to rcu_gp_ctr.
315 */
316 cmm_barrier();
317
318 /*
319 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
320 * model easier to understand. It does not have a big performance impact
321 * anyway, given this is the write-side.
322 */
323 cmm_smp_mb();
324
325 /*
326 * Wait for previous parity to be empty of readers.
327 */
328 update_counter_and_wait(); /* 1 -> 0, wait readers in parity 1 */
329
330 /* Finish waiting for reader threads before letting the old ptr being
331 * freed. Must be done within rcu_gp_lock because it iterates on reader
332 * threads. */
333 smp_mb_master(RCU_MB_GROUP);
334 out:
335 mutex_unlock(&rcu_gp_lock);
336 }
337
338 /*
339 * library wrappers to be used by non-LGPL compatible source code.
340 */
341
342 void rcu_read_lock(void)
343 {
344 _rcu_read_lock();
345 }
346
347 void rcu_read_unlock(void)
348 {
349 _rcu_read_unlock();
350 }
351
352 void rcu_register_thread(void)
353 {
354 rcu_reader.tid = pthread_self();
355 assert(rcu_reader.need_mb == 0);
356 assert(!(rcu_reader.ctr & RCU_GP_CTR_NEST_MASK));
357
358 mutex_lock(&rcu_gp_lock);
359 rcu_init(); /* In case gcc does not support constructor attribute */
360 cds_list_add(&rcu_reader.node, &registry);
361 mutex_unlock(&rcu_gp_lock);
362 }
363
364 void rcu_unregister_thread(void)
365 {
366 mutex_lock(&rcu_gp_lock);
367 cds_list_del(&rcu_reader.node);
368 mutex_unlock(&rcu_gp_lock);
369 }
370
371 #ifdef RCU_MEMBARRIER
372 void rcu_init(void)
373 {
374 if (init_done)
375 return;
376 init_done = 1;
377 if (!membarrier(MEMBARRIER_EXPEDITED | MEMBARRIER_QUERY))
378 has_sys_membarrier = 1;
379 }
380 #endif
381
382 #ifdef RCU_SIGNAL
383 static void sigrcu_handler(int signo, siginfo_t *siginfo, void *context)
384 {
385 /*
386 * Executing this cmm_smp_mb() is the only purpose of this signal handler.
387 * It punctually promotes cmm_barrier() into cmm_smp_mb() on every thread it is
388 * executed on.
389 */
390 cmm_smp_mb();
391 _CMM_STORE_SHARED(rcu_reader.need_mb, 0);
392 cmm_smp_mb();
393 }
394
395 /*
396 * rcu_init constructor. Called when the library is linked, but also when
397 * reader threads are calling rcu_register_thread().
398 * Should only be called by a single thread at a given time. This is ensured by
399 * holing the rcu_gp_lock from rcu_register_thread() or by running at library
400 * load time, which should not be executed by multiple threads nor concurrently
401 * with rcu_register_thread() anyway.
402 */
403 void rcu_init(void)
404 {
405 struct sigaction act;
406 int ret;
407
408 if (init_done)
409 return;
410 init_done = 1;
411
412 act.sa_sigaction = sigrcu_handler;
413 act.sa_flags = SA_SIGINFO | SA_RESTART;
414 sigemptyset(&act.sa_mask);
415 ret = sigaction(SIGRCU, &act, NULL);
416 if (ret) {
417 perror("Error in sigaction");
418 exit(-1);
419 }
420 }
421
422 void rcu_exit(void)
423 {
424 struct sigaction act;
425 int ret;
426
427 ret = sigaction(SIGRCU, NULL, &act);
428 if (ret) {
429 perror("Error in sigaction");
430 exit(-1);
431 }
432 assert(act.sa_sigaction == sigrcu_handler);
433 assert(cds_list_empty(&registry));
434 }
435
436 #endif /* #ifdef RCU_SIGNAL */
437
438 #include "urcu-call-rcu-impl.h"
439 #include "urcu-defer-impl.h"
This page took 0.040562 seconds and 4 git commands to generate.