urcu-mb/signal/membarrier: improve 2-phase wait scheme
[urcu.git] / urcu-bp.c
CommitLineData
fdee2e6d
MD
1/*
2 * urcu-bp.c
3 *
4 * Userspace RCU library, "bulletproof" version.
5 *
6982d6d7 6 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
fdee2e6d
MD
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
0617bf4c 26#define _GNU_SOURCE
71c811bf 27#define _LGPL_SOURCE
fdee2e6d
MD
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
d73fb81f 39#include "urcu/wfcqueue.h"
57760d44 40#include "urcu/map/urcu-bp.h"
af7c2dbe 41#include "urcu/static/urcu-bp.h"
618b2595 42#include "urcu-pointer.h"
bd252a04 43#include "urcu/tls-compat.h"
71c811bf 44
4a6d7378
MD
45#include "urcu-die.h"
46
fdee2e6d 47/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
71c811bf 48#undef _LGPL_SOURCE
fdee2e6d 49#include "urcu-bp.h"
71c811bf 50#define _LGPL_SOURCE
fdee2e6d 51
4c1ae2ea
MD
52#ifndef MAP_ANONYMOUS
53#define MAP_ANONYMOUS MAP_ANON
54#endif
55
c7eaf61c
MD
56#ifdef __linux__
57static
58void *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
45a4872f
MD
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*/
c7eaf61c
MD
72static
73void *mremap_wrapper(void *old_address, size_t old_size,
74 size_t new_size, int flags)
45a4872f 75{
dc745ef6 76 void *new_address;
45a4872f
MD
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
fdee2e6d
MD
94/* Sleep delay in us */
95#define RCU_SLEEP_DELAY 1000
96#define ARENA_INIT_ALLOC 16
97
b7b6a8f5
PB
98/*
99 * Active attempts to check for reader Q.S. before calling sleep().
100 */
101#define RCU_QS_ACTIVE_ATTEMPTS 100
102
02be5561 103void __attribute__((destructor)) rcu_bp_exit(void);
fdee2e6d 104
6abb4bd5 105static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
fdee2e6d
MD
106
107#ifdef DEBUG_YIELD
1de4df4b
MD
108unsigned int rcu_yield_active;
109DEFINE_URCU_TLS(unsigned int, rcu_rand_yield);
fdee2e6d
MD
110#endif
111
112/*
113 * Global grace period counter.
02be5561 114 * Contains the current RCU_GP_CTR_PHASE.
fdee2e6d
MD
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 */
02be5561 118long rcu_gp_ctr = RCU_GP_COUNT;
fdee2e6d
MD
119
120/*
121 * Pointer to registry elements. Written to only by each individual reader. Read
122 * by both the reader and the writers.
123 */
bd252a04 124DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
fdee2e6d 125
16aa9ee8 126static CDS_LIST_HEAD(registry);
fdee2e6d
MD
127
128struct registry_arena {
129 void *p;
130 size_t len;
131 size_t used;
132};
133
134static struct registry_arena registry_arena;
135
4cf1675f
MD
136/* Saved fork signal mask, protected by rcu_gp_lock */
137static sigset_t saved_fork_signal_mask;
138
fdee2e6d
MD
139static void rcu_gc_registry(void);
140
6abb4bd5 141static void mutex_lock(pthread_mutex_t *mutex)
fdee2e6d
MD
142{
143 int ret;
144
145#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 146 ret = pthread_mutex_lock(mutex);
4a6d7378
MD
147 if (ret)
148 urcu_die(ret);
fdee2e6d 149#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 150 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
4a6d7378
MD
151 if (ret != EBUSY && ret != EINTR)
152 urcu_die(ret);
fdee2e6d
MD
153 poll(NULL,0,10);
154 }
155#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
156}
157
6abb4bd5 158static void mutex_unlock(pthread_mutex_t *mutex)
fdee2e6d
MD
159{
160 int ret;
161
6abb4bd5 162 ret = pthread_mutex_unlock(mutex);
4a6d7378
MD
163 if (ret)
164 urcu_die(ret);
fdee2e6d
MD
165}
166
bab44e28 167static void update_counter_and_wait(void)
fdee2e6d 168{
16aa9ee8 169 CDS_LIST_HEAD(qsreaders);
fdee2e6d 170 int wait_loops = 0;
02be5561 171 struct rcu_reader *index, *tmp;
fdee2e6d 172
32c15e4e 173 /* Switch parity: 0 -> 1, 1 -> 0 */
6cf3827c 174 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
2dfb8b5e
MD
175
176 /*
177 * Must commit qparity update to memory before waiting for other parity
178 * quiescent state. Failure to do so could result in the writer waiting
179 * forever while new readers are always accessing data (no progress).
6cf3827c 180 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
2dfb8b5e
MD
181 */
182
183 /*
5481ddb3 184 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
2dfb8b5e
MD
185 * model easier to understand. It does not have a big performance impact
186 * anyway, given this is the write-side.
187 */
5481ddb3 188 cmm_smp_mb();
2dfb8b5e 189
fdee2e6d 190 /*
02be5561 191 * Wait for each thread rcu_reader.ctr count to become 0.
fdee2e6d
MD
192 */
193 for (;;) {
194 wait_loops++;
16aa9ee8 195 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
fdee2e6d 196 if (!rcu_old_gp_ongoing(&index->ctr))
16aa9ee8 197 cds_list_move(&index->node, &qsreaders);
fdee2e6d
MD
198 }
199
16aa9ee8 200 if (cds_list_empty(&registry)) {
fdee2e6d
MD
201 break;
202 } else {
203 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
204 usleep(RCU_SLEEP_DELAY);
205 else
06f22bdb 206 caa_cpu_relax();
fdee2e6d
MD
207 }
208 }
209 /* put back the reader list in the registry */
16aa9ee8 210 cds_list_splice(&qsreaders, &registry);
fdee2e6d
MD
211}
212
213void synchronize_rcu(void)
214{
215 sigset_t newmask, oldmask;
216 int ret;
217
218 ret = sigemptyset(&newmask);
219 assert(!ret);
220 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
221 assert(!ret);
222
6abb4bd5 223 mutex_lock(&rcu_gp_lock);
fdee2e6d 224
16aa9ee8 225 if (cds_list_empty(&registry))
2dfb8b5e 226 goto out;
fdee2e6d
MD
227
228 /* All threads should read qparity before accessing data structure
2dfb8b5e 229 * where new ptr points to. */
fdee2e6d 230 /* Write new ptr before changing the qparity */
5481ddb3 231 cmm_smp_mb();
fdee2e6d 232
2dfb8b5e
MD
233 /* Remove old registry elements */
234 rcu_gc_registry();
fdee2e6d
MD
235
236 /*
237 * Wait for previous parity to be empty of readers.
238 */
2dfb8b5e 239 update_counter_and_wait(); /* 0 -> 1, wait readers in parity 0 */
fdee2e6d
MD
240
241 /*
5481ddb3 242 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
fdee2e6d
MD
243 * model easier to understand. It does not have a big performance impact
244 * anyway, given this is the write-side.
245 */
5481ddb3 246 cmm_smp_mb();
fdee2e6d 247
fdee2e6d 248 /*
2dfb8b5e 249 * Wait for previous parity to be empty of readers.
fdee2e6d 250 */
2dfb8b5e 251 update_counter_and_wait(); /* 1 -> 0, wait readers in parity 1 */
fdee2e6d
MD
252
253 /*
2dfb8b5e
MD
254 * Finish waiting for reader threads before letting the old ptr being
255 * freed.
fdee2e6d 256 */
5481ddb3 257 cmm_smp_mb();
2dfb8b5e 258out:
6abb4bd5 259 mutex_unlock(&rcu_gp_lock);
fdee2e6d
MD
260 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
261 assert(!ret);
262}
263
264/*
265 * library wrappers to be used by non-LGPL compatible source code.
266 */
267
268void rcu_read_lock(void)
269{
270 _rcu_read_lock();
271}
272
273void rcu_read_unlock(void)
274{
275 _rcu_read_unlock();
276}
277
278/*
279 * only grow for now.
280 */
281static void resize_arena(struct registry_arena *arena, size_t len)
282{
283 void *new_arena;
284
0617bf4c
MD
285 if (!arena->p)
286 new_arena = mmap(arena->p, len,
287 PROT_READ | PROT_WRITE,
288 MAP_ANONYMOUS | MAP_PRIVATE,
289 -1, 0);
290 else
c7eaf61c
MD
291 new_arena = mremap_wrapper(arena->p, arena->len,
292 len, MREMAP_MAYMOVE);
0617bf4c
MD
293 assert(new_arena != MAP_FAILED);
294
fdee2e6d
MD
295 /*
296 * re-used the same region ?
297 */
298 if (new_arena == arena->p)
299 return;
300
fdee2e6d
MD
301 bzero(new_arena + arena->len, len - arena->len);
302 arena->p = new_arena;
303}
304
305/* Called with signals off and mutex locked */
306static void add_thread(void)
307{
02be5561 308 struct rcu_reader *rcu_reader_reg;
fdee2e6d
MD
309
310 if (registry_arena.len
02be5561 311 < registry_arena.used + sizeof(struct rcu_reader))
fdee2e6d 312 resize_arena(&registry_arena,
2f8a5ae7 313 caa_max(registry_arena.len << 1, ARENA_INIT_ALLOC));
fdee2e6d
MD
314 /*
315 * Find a free spot.
316 */
02be5561
MD
317 for (rcu_reader_reg = registry_arena.p;
318 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
319 rcu_reader_reg++) {
320 if (!rcu_reader_reg->alloc)
fdee2e6d
MD
321 break;
322 }
02be5561
MD
323 rcu_reader_reg->alloc = 1;
324 registry_arena.used += sizeof(struct rcu_reader);
fdee2e6d
MD
325
326 /* Add to registry */
02be5561
MD
327 rcu_reader_reg->tid = pthread_self();
328 assert(rcu_reader_reg->ctr == 0);
16aa9ee8 329 cds_list_add(&rcu_reader_reg->node, &registry);
bd252a04 330 URCU_TLS(rcu_reader) = rcu_reader_reg;
fdee2e6d
MD
331}
332
333/* Called with signals off and mutex locked */
334static void rcu_gc_registry(void)
335{
02be5561 336 struct rcu_reader *rcu_reader_reg;
fdee2e6d
MD
337 pthread_t tid;
338 int ret;
339
02be5561
MD
340 for (rcu_reader_reg = registry_arena.p;
341 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
342 rcu_reader_reg++) {
343 if (!rcu_reader_reg->alloc)
fdee2e6d 344 continue;
02be5561 345 tid = rcu_reader_reg->tid;
fdee2e6d
MD
346 ret = pthread_kill(tid, 0);
347 assert(ret != EINVAL);
348 if (ret == ESRCH) {
16aa9ee8 349 cds_list_del(&rcu_reader_reg->node);
79266051 350 rcu_reader_reg->ctr = 0;
02be5561
MD
351 rcu_reader_reg->alloc = 0;
352 registry_arena.used -= sizeof(struct rcu_reader);
fdee2e6d
MD
353 }
354 }
355}
356
357/* Disable signals, take mutex, add to registry */
358void rcu_bp_register(void)
359{
360 sigset_t newmask, oldmask;
361 int ret;
362
363 ret = sigemptyset(&newmask);
364 assert(!ret);
365 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
366 assert(!ret);
367
368 /*
369 * Check if a signal concurrently registered our thread since
370 * the check in rcu_read_lock(). */
bd252a04 371 if (URCU_TLS(rcu_reader))
fdee2e6d
MD
372 goto end;
373
6abb4bd5 374 mutex_lock(&rcu_gp_lock);
fdee2e6d 375 add_thread();
6abb4bd5 376 mutex_unlock(&rcu_gp_lock);
fdee2e6d
MD
377end:
378 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
379 assert(!ret);
380}
381
9380711a 382void rcu_bp_exit(void)
fdee2e6d 383{
9380711a
MD
384 if (registry_arena.p)
385 munmap(registry_arena.p, registry_arena.len);
fdee2e6d 386}
4cf1675f
MD
387
388/*
389 * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
390 * a concurrent thread executing with this same lock held. This ensures that the
391 * registry is in a coherent state in the child.
392 */
393void rcu_bp_before_fork(void)
394{
395 sigset_t newmask, oldmask;
396 int ret;
397
398 ret = sigemptyset(&newmask);
399 assert(!ret);
400 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
401 assert(!ret);
402 mutex_lock(&rcu_gp_lock);
403 saved_fork_signal_mask = oldmask;
404}
405
406void rcu_bp_after_fork_parent(void)
407{
408 sigset_t oldmask;
409 int ret;
410
411 oldmask = saved_fork_signal_mask;
412 mutex_unlock(&rcu_gp_lock);
413 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
414 assert(!ret);
415}
416
417void rcu_bp_after_fork_child(void)
418{
419 sigset_t oldmask;
420 int ret;
421
422 rcu_gc_registry();
423 oldmask = saved_fork_signal_mask;
424 mutex_unlock(&rcu_gp_lock);
425 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
426 assert(!ret);
427}
5e77fc1f 428
9b7981bb
MD
429void *rcu_dereference_sym_bp(void *p)
430{
431 return _rcu_dereference(p);
432}
433
5efd3cd2
MD
434void *rcu_set_pointer_sym_bp(void **p, void *v)
435{
436 cmm_wmb();
424d4ed5
MD
437 uatomic_set(p, v);
438 return v;
5efd3cd2
MD
439}
440
441void *rcu_xchg_pointer_sym_bp(void **p, void *v)
442{
443 cmm_wmb();
444 return uatomic_xchg(p, v);
445}
446
447void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
448{
449 cmm_wmb();
450 return uatomic_cmpxchg(p, old, _new);
451}
452
5e6b23a6 453DEFINE_RCU_FLAVOR(rcu_flavor);
541d828d 454
5e77fc1f 455#include "urcu-call-rcu-impl.h"
0376e7b2 456#include "urcu-defer-impl.h"
This page took 0.073779 seconds and 4 git commands to generate.