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