Fix: compat futex duplicated lock and completion
[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
c13c2e55 112struct rcu_gp rcu_gp = { .ctr = RCU_GP_COUNT };
fdee2e6d
MD
113
114/*
115 * Pointer to registry elements. Written to only by each individual reader. Read
116 * by both the reader and the writers.
117 */
bd252a04 118DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
fdee2e6d 119
16aa9ee8 120static CDS_LIST_HEAD(registry);
fdee2e6d
MD
121
122struct registry_arena {
123 void *p;
124 size_t len;
125 size_t used;
126};
127
128static struct registry_arena registry_arena;
129
4cf1675f
MD
130/* Saved fork signal mask, protected by rcu_gp_lock */
131static sigset_t saved_fork_signal_mask;
132
fdee2e6d
MD
133static void rcu_gc_registry(void);
134
6abb4bd5 135static void mutex_lock(pthread_mutex_t *mutex)
fdee2e6d
MD
136{
137 int ret;
138
139#ifndef DISTRUST_SIGNALS_EXTREME
6abb4bd5 140 ret = pthread_mutex_lock(mutex);
4a6d7378
MD
141 if (ret)
142 urcu_die(ret);
fdee2e6d 143#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
6abb4bd5 144 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
4a6d7378
MD
145 if (ret != EBUSY && ret != EINTR)
146 urcu_die(ret);
fdee2e6d
MD
147 poll(NULL,0,10);
148 }
149#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
150}
151
6abb4bd5 152static void mutex_unlock(pthread_mutex_t *mutex)
fdee2e6d
MD
153{
154 int ret;
155
6abb4bd5 156 ret = pthread_mutex_unlock(mutex);
4a6d7378
MD
157 if (ret)
158 urcu_die(ret);
fdee2e6d
MD
159}
160
52c75091
MD
161static void wait_for_readers(struct cds_list_head *input_readers,
162 struct cds_list_head *cur_snap_readers,
163 struct cds_list_head *qsreaders)
fdee2e6d 164{
fdee2e6d 165 int wait_loops = 0;
02be5561 166 struct rcu_reader *index, *tmp;
fdee2e6d 167
fdee2e6d 168 /*
dd61d077
MD
169 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
170 * indicate quiescence (not nested), or observe the current
c13c2e55 171 * rcu_gp.ctr value.
fdee2e6d
MD
172 */
173 for (;;) {
174 wait_loops++;
52c75091
MD
175 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
176 switch (rcu_reader_state(&index->ctr)) {
177 case RCU_READER_ACTIVE_CURRENT:
178 if (cur_snap_readers) {
179 cds_list_move(&index->node,
180 cur_snap_readers);
181 break;
182 }
183 /* Fall-through */
184 case RCU_READER_INACTIVE:
185 cds_list_move(&index->node, qsreaders);
186 break;
187 case RCU_READER_ACTIVE_OLD:
188 /*
189 * Old snapshot. Leaving node in
190 * input_readers will make us busy-loop
191 * until the snapshot becomes current or
192 * the reader becomes inactive.
193 */
194 break;
195 }
fdee2e6d
MD
196 }
197
52c75091 198 if (cds_list_empty(input_readers)) {
fdee2e6d
MD
199 break;
200 } else {
201 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
202 usleep(RCU_SLEEP_DELAY);
203 else
06f22bdb 204 caa_cpu_relax();
fdee2e6d
MD
205 }
206 }
fdee2e6d
MD
207}
208
209void synchronize_rcu(void)
210{
52c75091
MD
211 CDS_LIST_HEAD(cur_snap_readers);
212 CDS_LIST_HEAD(qsreaders);
fdee2e6d
MD
213 sigset_t newmask, oldmask;
214 int ret;
215
6ed4b2e6 216 ret = sigfillset(&newmask);
fdee2e6d 217 assert(!ret);
6ed4b2e6 218 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
fdee2e6d
MD
219 assert(!ret);
220
6abb4bd5 221 mutex_lock(&rcu_gp_lock);
fdee2e6d 222
16aa9ee8 223 if (cds_list_empty(&registry))
2dfb8b5e 224 goto out;
fdee2e6d
MD
225
226 /* All threads should read qparity before accessing data structure
2dfb8b5e 227 * where new ptr points to. */
fdee2e6d 228 /* Write new ptr before changing the qparity */
5481ddb3 229 cmm_smp_mb();
fdee2e6d 230
2dfb8b5e
MD
231 /* Remove old registry elements */
232 rcu_gc_registry();
fdee2e6d
MD
233
234 /*
dd61d077
MD
235 * Wait for readers to observe original parity or be quiescent.
236 */
52c75091 237 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
dd61d077
MD
238
239 /*
240 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
241 * model easier to understand. It does not have a big performance impact
242 * anyway, given this is the write-side.
243 */
244 cmm_smp_mb();
245
246 /* Switch parity: 0 -> 1, 1 -> 0 */
c13c2e55 247 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr ^ RCU_GP_CTR_PHASE);
dd61d077
MD
248
249 /*
250 * Must commit qparity update to memory before waiting for other parity
251 * quiescent state. Failure to do so could result in the writer waiting
252 * forever while new readers are always accessing data (no progress).
253 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
fdee2e6d 254 */
fdee2e6d
MD
255
256 /*
5481ddb3 257 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
fdee2e6d
MD
258 * model easier to understand. It does not have a big performance impact
259 * anyway, given this is the write-side.
260 */
5481ddb3 261 cmm_smp_mb();
fdee2e6d 262
fdee2e6d 263 /*
dd61d077 264 * Wait for readers to observe new parity or be quiescent.
fdee2e6d 265 */
52c75091
MD
266 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
267
268 /*
269 * Put quiescent reader list back into registry.
270 */
271 cds_list_splice(&qsreaders, &registry);
fdee2e6d
MD
272
273 /*
2dfb8b5e
MD
274 * Finish waiting for reader threads before letting the old ptr being
275 * freed.
fdee2e6d 276 */
5481ddb3 277 cmm_smp_mb();
2dfb8b5e 278out:
6abb4bd5 279 mutex_unlock(&rcu_gp_lock);
fdee2e6d
MD
280 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
281 assert(!ret);
282}
283
284/*
285 * library wrappers to be used by non-LGPL compatible source code.
286 */
287
288void rcu_read_lock(void)
289{
290 _rcu_read_lock();
291}
292
293void rcu_read_unlock(void)
294{
295 _rcu_read_unlock();
296}
297
882f3357
MD
298int rcu_read_ongoing(void)
299{
300 return _rcu_read_ongoing();
301}
302
fdee2e6d
MD
303/*
304 * only grow for now.
305 */
306static void resize_arena(struct registry_arena *arena, size_t len)
307{
9d8612b7
MD
308 void *new_p;
309 size_t old_len;
310
311 old_len = arena->len;
fdee2e6d 312
0617bf4c 313 if (!arena->p)
9d8612b7
MD
314 new_p = mmap(arena->p, len,
315 PROT_READ | PROT_WRITE,
316 MAP_ANONYMOUS | MAP_PRIVATE,
317 -1, 0);
0617bf4c 318 else
9d8612b7
MD
319 new_p = mremap_wrapper(arena->p, old_len,
320 len, MREMAP_MAYMOVE);
321 assert(new_p != MAP_FAILED);
322
323 /*
324 * Zero the newly allocated memory. Since mmap() does not
325 * clearly specify if memory is zeroed or not (although it is
326 * very likely that it is), be extra careful by not expecting
327 * the new range to be zeroed by mremap.
328 */
329 bzero(new_p + old_len, len - old_len);
0617bf4c 330
fdee2e6d 331 /*
9d8612b7
MD
332 * If we did not re-use the same region, we need to update the
333 * arena pointer.
fdee2e6d 334 */
9d8612b7
MD
335 if (new_p != arena->p)
336 arena->p = new_p;
fdee2e6d 337
9d8612b7 338 arena->len = len;
fdee2e6d
MD
339}
340
341/* Called with signals off and mutex locked */
342static void add_thread(void)
343{
02be5561 344 struct rcu_reader *rcu_reader_reg;
fdee2e6d
MD
345
346 if (registry_arena.len
02be5561 347 < registry_arena.used + sizeof(struct rcu_reader))
fdee2e6d 348 resize_arena(&registry_arena,
2f8a5ae7 349 caa_max(registry_arena.len << 1, ARENA_INIT_ALLOC));
fdee2e6d
MD
350 /*
351 * Find a free spot.
352 */
02be5561
MD
353 for (rcu_reader_reg = registry_arena.p;
354 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
355 rcu_reader_reg++) {
356 if (!rcu_reader_reg->alloc)
fdee2e6d
MD
357 break;
358 }
02be5561
MD
359 rcu_reader_reg->alloc = 1;
360 registry_arena.used += sizeof(struct rcu_reader);
fdee2e6d
MD
361
362 /* Add to registry */
02be5561
MD
363 rcu_reader_reg->tid = pthread_self();
364 assert(rcu_reader_reg->ctr == 0);
16aa9ee8 365 cds_list_add(&rcu_reader_reg->node, &registry);
bd252a04 366 URCU_TLS(rcu_reader) = rcu_reader_reg;
fdee2e6d
MD
367}
368
369/* Called with signals off and mutex locked */
370static void rcu_gc_registry(void)
371{
02be5561 372 struct rcu_reader *rcu_reader_reg;
fdee2e6d
MD
373 pthread_t tid;
374 int ret;
375
02be5561
MD
376 for (rcu_reader_reg = registry_arena.p;
377 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
378 rcu_reader_reg++) {
379 if (!rcu_reader_reg->alloc)
fdee2e6d 380 continue;
02be5561 381 tid = rcu_reader_reg->tid;
fdee2e6d
MD
382 ret = pthread_kill(tid, 0);
383 assert(ret != EINVAL);
384 if (ret == ESRCH) {
16aa9ee8 385 cds_list_del(&rcu_reader_reg->node);
79266051 386 rcu_reader_reg->ctr = 0;
02be5561
MD
387 rcu_reader_reg->alloc = 0;
388 registry_arena.used -= sizeof(struct rcu_reader);
fdee2e6d
MD
389 }
390 }
391}
392
393/* Disable signals, take mutex, add to registry */
394void rcu_bp_register(void)
395{
396 sigset_t newmask, oldmask;
397 int ret;
398
6ed4b2e6 399 ret = sigfillset(&newmask);
fdee2e6d 400 assert(!ret);
6ed4b2e6 401 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
fdee2e6d
MD
402 assert(!ret);
403
404 /*
405 * Check if a signal concurrently registered our thread since
406 * the check in rcu_read_lock(). */
bd252a04 407 if (URCU_TLS(rcu_reader))
fdee2e6d
MD
408 goto end;
409
6abb4bd5 410 mutex_lock(&rcu_gp_lock);
fdee2e6d 411 add_thread();
6abb4bd5 412 mutex_unlock(&rcu_gp_lock);
fdee2e6d
MD
413end:
414 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
415 assert(!ret);
416}
417
9380711a 418void rcu_bp_exit(void)
fdee2e6d 419{
9380711a
MD
420 if (registry_arena.p)
421 munmap(registry_arena.p, registry_arena.len);
fdee2e6d 422}
4cf1675f
MD
423
424/*
425 * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
426 * a concurrent thread executing with this same lock held. This ensures that the
427 * registry is in a coherent state in the child.
428 */
429void rcu_bp_before_fork(void)
430{
431 sigset_t newmask, oldmask;
432 int ret;
433
6ed4b2e6 434 ret = sigfillset(&newmask);
4cf1675f 435 assert(!ret);
6ed4b2e6 436 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
4cf1675f
MD
437 assert(!ret);
438 mutex_lock(&rcu_gp_lock);
439 saved_fork_signal_mask = oldmask;
440}
441
442void rcu_bp_after_fork_parent(void)
443{
444 sigset_t oldmask;
445 int ret;
446
447 oldmask = saved_fork_signal_mask;
448 mutex_unlock(&rcu_gp_lock);
449 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
450 assert(!ret);
451}
452
453void rcu_bp_after_fork_child(void)
454{
455 sigset_t oldmask;
456 int ret;
457
458 rcu_gc_registry();
459 oldmask = saved_fork_signal_mask;
460 mutex_unlock(&rcu_gp_lock);
461 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
462 assert(!ret);
463}
5e77fc1f 464
9b7981bb
MD
465void *rcu_dereference_sym_bp(void *p)
466{
467 return _rcu_dereference(p);
468}
469
5efd3cd2
MD
470void *rcu_set_pointer_sym_bp(void **p, void *v)
471{
472 cmm_wmb();
424d4ed5
MD
473 uatomic_set(p, v);
474 return v;
5efd3cd2
MD
475}
476
477void *rcu_xchg_pointer_sym_bp(void **p, void *v)
478{
479 cmm_wmb();
480 return uatomic_xchg(p, v);
481}
482
483void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
484{
485 cmm_wmb();
486 return uatomic_cmpxchg(p, old, _new);
487}
488
5e6b23a6 489DEFINE_RCU_FLAVOR(rcu_flavor);
541d828d 490
5e77fc1f 491#include "urcu-call-rcu-impl.h"
0376e7b2 492#include "urcu-defer-impl.h"
This page took 0.080765 seconds and 4 git commands to generate.