Add rcu_read_ongoing() API to each urcu flavor
[urcu.git] / urcu-bp.c
1 /*
2 * urcu-bp.c
3 *
4 * Userspace RCU library, "bulletproof" version.
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 _GNU_SOURCE
27 #define _LGPL_SOURCE
28 #include <stdio.h>
29 #include <pthread.h>
30 #include <signal.h>
31 #include <assert.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <errno.h>
35 #include <poll.h>
36 #include <unistd.h>
37 #include <sys/mman.h>
38
39 #include "urcu/wfcqueue.h"
40 #include "urcu/map/urcu-bp.h"
41 #include "urcu/static/urcu-bp.h"
42 #include "urcu-pointer.h"
43 #include "urcu/tls-compat.h"
44
45 #include "urcu-die.h"
46
47 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
48 #undef _LGPL_SOURCE
49 #include "urcu-bp.h"
50 #define _LGPL_SOURCE
51
52 #ifndef MAP_ANONYMOUS
53 #define MAP_ANONYMOUS MAP_ANON
54 #endif
55
56 #ifdef __linux__
57 static
58 void *mremap_wrapper(void *old_address, size_t old_size,
59 size_t new_size, int flags)
60 {
61 return mremap(old_address, old_size, new_size, flags);
62 }
63 #else
64
65 #define MREMAP_MAYMOVE 1
66 #define MREMAP_FIXED 2
67
68 /*
69 * mremap wrapper for non-Linux systems. Maps a RW, anonymous private mapping.
70 * This is not generic.
71 */
72 static
73 void *mremap_wrapper(void *old_address, size_t old_size,
74 size_t new_size, int flags)
75 {
76 void *new_address;
77
78 assert(flags & MREMAP_MAYMOVE);
79 assert(!(flags & MREMAP_FIXED));
80 new_address = mmap(old_address, new_size,
81 PROT_READ | PROT_WRITE,
82 MAP_ANONYMOUS | MAP_PRIVATE,
83 -1, 0);
84 if (new_address == MAP_FAILED)
85 return MAP_FAILED;
86 if (old_address) {
87 memcpy(new_address, old_address, old_size);
88 munmap(old_address, old_size);
89 }
90 return new_address;
91 }
92 #endif
93
94 /* Sleep delay in us */
95 #define RCU_SLEEP_DELAY 1000
96 #define ARENA_INIT_ALLOC 16
97
98 /*
99 * Active attempts to check for reader Q.S. before calling sleep().
100 */
101 #define RCU_QS_ACTIVE_ATTEMPTS 100
102
103 void __attribute__((destructor)) rcu_bp_exit(void);
104
105 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
106
107 #ifdef DEBUG_YIELD
108 unsigned int rcu_yield_active;
109 DEFINE_URCU_TLS(unsigned int, rcu_rand_yield);
110 #endif
111
112 /*
113 * Global grace period counter.
114 * Contains the current RCU_GP_CTR_PHASE.
115 * Also has a RCU_GP_COUNT of 1, to accelerate the reader fast path.
116 * Written to only by writer with mutex taken. Read by both writer and readers.
117 */
118 unsigned long rcu_gp_ctr = RCU_GP_COUNT;
119
120 /*
121 * Pointer to registry elements. Written to only by each individual reader. Read
122 * by both the reader and the writers.
123 */
124 DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
125
126 static CDS_LIST_HEAD(registry);
127
128 struct registry_arena {
129 void *p;
130 size_t len;
131 size_t used;
132 };
133
134 static struct registry_arena registry_arena;
135
136 /* Saved fork signal mask, protected by rcu_gp_lock */
137 static sigset_t saved_fork_signal_mask;
138
139 static void rcu_gc_registry(void);
140
141 static void mutex_lock(pthread_mutex_t *mutex)
142 {
143 int ret;
144
145 #ifndef DISTRUST_SIGNALS_EXTREME
146 ret = pthread_mutex_lock(mutex);
147 if (ret)
148 urcu_die(ret);
149 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
150 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
151 if (ret != EBUSY && ret != EINTR)
152 urcu_die(ret);
153 poll(NULL,0,10);
154 }
155 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
156 }
157
158 static void mutex_unlock(pthread_mutex_t *mutex)
159 {
160 int ret;
161
162 ret = pthread_mutex_unlock(mutex);
163 if (ret)
164 urcu_die(ret);
165 }
166
167 static void wait_for_readers(struct cds_list_head *input_readers,
168 struct cds_list_head *cur_snap_readers,
169 struct cds_list_head *qsreaders)
170 {
171 int wait_loops = 0;
172 struct rcu_reader *index, *tmp;
173
174 /*
175 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
176 * indicate quiescence (not nested), or observe the current
177 * rcu_gp_ctr value.
178 */
179 for (;;) {
180 wait_loops++;
181 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
182 switch (rcu_reader_state(&index->ctr)) {
183 case RCU_READER_ACTIVE_CURRENT:
184 if (cur_snap_readers) {
185 cds_list_move(&index->node,
186 cur_snap_readers);
187 break;
188 }
189 /* Fall-through */
190 case RCU_READER_INACTIVE:
191 cds_list_move(&index->node, qsreaders);
192 break;
193 case RCU_READER_ACTIVE_OLD:
194 /*
195 * Old snapshot. Leaving node in
196 * input_readers will make us busy-loop
197 * until the snapshot becomes current or
198 * the reader becomes inactive.
199 */
200 break;
201 }
202 }
203
204 if (cds_list_empty(input_readers)) {
205 break;
206 } else {
207 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
208 usleep(RCU_SLEEP_DELAY);
209 else
210 caa_cpu_relax();
211 }
212 }
213 }
214
215 void synchronize_rcu(void)
216 {
217 CDS_LIST_HEAD(cur_snap_readers);
218 CDS_LIST_HEAD(qsreaders);
219 sigset_t newmask, oldmask;
220 int ret;
221
222 ret = sigemptyset(&newmask);
223 assert(!ret);
224 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
225 assert(!ret);
226
227 mutex_lock(&rcu_gp_lock);
228
229 if (cds_list_empty(&registry))
230 goto out;
231
232 /* All threads should read qparity before accessing data structure
233 * where new ptr points to. */
234 /* Write new ptr before changing the qparity */
235 cmm_smp_mb();
236
237 /* Remove old registry elements */
238 rcu_gc_registry();
239
240 /*
241 * Wait for readers to observe original parity or be quiescent.
242 */
243 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
244
245 /*
246 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
247 * model easier to understand. It does not have a big performance impact
248 * anyway, given this is the write-side.
249 */
250 cmm_smp_mb();
251
252 /* Switch parity: 0 -> 1, 1 -> 0 */
253 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
254
255 /*
256 * Must commit qparity update to memory before waiting for other parity
257 * quiescent state. Failure to do so could result in the writer waiting
258 * forever while new readers are always accessing data (no progress).
259 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
260 */
261
262 /*
263 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
264 * model easier to understand. It does not have a big performance impact
265 * anyway, given this is the write-side.
266 */
267 cmm_smp_mb();
268
269 /*
270 * Wait for readers to observe new parity or be quiescent.
271 */
272 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
273
274 /*
275 * Put quiescent reader list back into registry.
276 */
277 cds_list_splice(&qsreaders, &registry);
278
279 /*
280 * Finish waiting for reader threads before letting the old ptr being
281 * freed.
282 */
283 cmm_smp_mb();
284 out:
285 mutex_unlock(&rcu_gp_lock);
286 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
287 assert(!ret);
288 }
289
290 /*
291 * library wrappers to be used by non-LGPL compatible source code.
292 */
293
294 void rcu_read_lock(void)
295 {
296 _rcu_read_lock();
297 }
298
299 void rcu_read_unlock(void)
300 {
301 _rcu_read_unlock();
302 }
303
304 int rcu_read_ongoing(void)
305 {
306 return _rcu_read_ongoing();
307 }
308
309 /*
310 * only grow for now.
311 */
312 static void resize_arena(struct registry_arena *arena, size_t len)
313 {
314 void *new_arena;
315
316 if (!arena->p)
317 new_arena = mmap(arena->p, len,
318 PROT_READ | PROT_WRITE,
319 MAP_ANONYMOUS | MAP_PRIVATE,
320 -1, 0);
321 else
322 new_arena = mremap_wrapper(arena->p, arena->len,
323 len, MREMAP_MAYMOVE);
324 assert(new_arena != MAP_FAILED);
325
326 /*
327 * re-used the same region ?
328 */
329 if (new_arena == arena->p)
330 return;
331
332 bzero(new_arena + arena->len, len - arena->len);
333 arena->p = new_arena;
334 }
335
336 /* Called with signals off and mutex locked */
337 static void add_thread(void)
338 {
339 struct rcu_reader *rcu_reader_reg;
340
341 if (registry_arena.len
342 < registry_arena.used + sizeof(struct rcu_reader))
343 resize_arena(&registry_arena,
344 caa_max(registry_arena.len << 1, ARENA_INIT_ALLOC));
345 /*
346 * Find a free spot.
347 */
348 for (rcu_reader_reg = registry_arena.p;
349 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
350 rcu_reader_reg++) {
351 if (!rcu_reader_reg->alloc)
352 break;
353 }
354 rcu_reader_reg->alloc = 1;
355 registry_arena.used += sizeof(struct rcu_reader);
356
357 /* Add to registry */
358 rcu_reader_reg->tid = pthread_self();
359 assert(rcu_reader_reg->ctr == 0);
360 cds_list_add(&rcu_reader_reg->node, &registry);
361 URCU_TLS(rcu_reader) = rcu_reader_reg;
362 }
363
364 /* Called with signals off and mutex locked */
365 static void rcu_gc_registry(void)
366 {
367 struct rcu_reader *rcu_reader_reg;
368 pthread_t tid;
369 int ret;
370
371 for (rcu_reader_reg = registry_arena.p;
372 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
373 rcu_reader_reg++) {
374 if (!rcu_reader_reg->alloc)
375 continue;
376 tid = rcu_reader_reg->tid;
377 ret = pthread_kill(tid, 0);
378 assert(ret != EINVAL);
379 if (ret == ESRCH) {
380 cds_list_del(&rcu_reader_reg->node);
381 rcu_reader_reg->ctr = 0;
382 rcu_reader_reg->alloc = 0;
383 registry_arena.used -= sizeof(struct rcu_reader);
384 }
385 }
386 }
387
388 /* Disable signals, take mutex, add to registry */
389 void rcu_bp_register(void)
390 {
391 sigset_t newmask, oldmask;
392 int ret;
393
394 ret = sigemptyset(&newmask);
395 assert(!ret);
396 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
397 assert(!ret);
398
399 /*
400 * Check if a signal concurrently registered our thread since
401 * the check in rcu_read_lock(). */
402 if (URCU_TLS(rcu_reader))
403 goto end;
404
405 mutex_lock(&rcu_gp_lock);
406 add_thread();
407 mutex_unlock(&rcu_gp_lock);
408 end:
409 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
410 assert(!ret);
411 }
412
413 void rcu_bp_exit(void)
414 {
415 if (registry_arena.p)
416 munmap(registry_arena.p, registry_arena.len);
417 }
418
419 /*
420 * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
421 * a concurrent thread executing with this same lock held. This ensures that the
422 * registry is in a coherent state in the child.
423 */
424 void rcu_bp_before_fork(void)
425 {
426 sigset_t newmask, oldmask;
427 int ret;
428
429 ret = sigemptyset(&newmask);
430 assert(!ret);
431 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
432 assert(!ret);
433 mutex_lock(&rcu_gp_lock);
434 saved_fork_signal_mask = oldmask;
435 }
436
437 void rcu_bp_after_fork_parent(void)
438 {
439 sigset_t oldmask;
440 int ret;
441
442 oldmask = saved_fork_signal_mask;
443 mutex_unlock(&rcu_gp_lock);
444 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
445 assert(!ret);
446 }
447
448 void rcu_bp_after_fork_child(void)
449 {
450 sigset_t oldmask;
451 int ret;
452
453 rcu_gc_registry();
454 oldmask = saved_fork_signal_mask;
455 mutex_unlock(&rcu_gp_lock);
456 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
457 assert(!ret);
458 }
459
460 void *rcu_dereference_sym_bp(void *p)
461 {
462 return _rcu_dereference(p);
463 }
464
465 void *rcu_set_pointer_sym_bp(void **p, void *v)
466 {
467 cmm_wmb();
468 uatomic_set(p, v);
469 return v;
470 }
471
472 void *rcu_xchg_pointer_sym_bp(void **p, void *v)
473 {
474 cmm_wmb();
475 return uatomic_xchg(p, v);
476 }
477
478 void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
479 {
480 cmm_wmb();
481 return uatomic_cmpxchg(p, old, _new);
482 }
483
484 DEFINE_RCU_FLAVOR(rcu_flavor);
485
486 #include "urcu-call-rcu-impl.h"
487 #include "urcu-defer-impl.h"
This page took 0.052902 seconds and 4 git commands to generate.