urcu-bp: improve 2-phase wait scheme
[urcu.git] / urcu-bp.c
... / ...
CommitLineData
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__
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
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*/
72static
73void *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
103void __attribute__((destructor)) rcu_bp_exit(void);
104
105static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
106
107#ifdef DEBUG_YIELD
108unsigned int rcu_yield_active;
109DEFINE_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 */
118long 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 */
124DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
125
126static CDS_LIST_HEAD(registry);
127
128struct registry_arena {
129 void *p;
130 size_t len;
131 size_t used;
132};
133
134static struct registry_arena registry_arena;
135
136/* Saved fork signal mask, protected by rcu_gp_lock */
137static sigset_t saved_fork_signal_mask;
138
139static void rcu_gc_registry(void);
140
141static 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
158static 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
167static void wait_for_readers(void)
168{
169 CDS_LIST_HEAD(qsreaders);
170 int wait_loops = 0;
171 struct rcu_reader *index, *tmp;
172
173 /*
174 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
175 * indicate quiescence (not nested), or observe the current
176 * rcu_gp_ctr value.
177 */
178 for (;;) {
179 wait_loops++;
180 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
181 if (!rcu_old_gp_ongoing(&index->ctr))
182 cds_list_move(&index->node, &qsreaders);
183 }
184
185 if (cds_list_empty(&registry)) {
186 break;
187 } else {
188 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
189 usleep(RCU_SLEEP_DELAY);
190 else
191 caa_cpu_relax();
192 }
193 }
194 /* put back the reader list in the registry */
195 cds_list_splice(&qsreaders, &registry);
196}
197
198void synchronize_rcu(void)
199{
200 sigset_t newmask, oldmask;
201 int ret;
202
203 ret = sigemptyset(&newmask);
204 assert(!ret);
205 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
206 assert(!ret);
207
208 mutex_lock(&rcu_gp_lock);
209
210 if (cds_list_empty(&registry))
211 goto out;
212
213 /* All threads should read qparity before accessing data structure
214 * where new ptr points to. */
215 /* Write new ptr before changing the qparity */
216 cmm_smp_mb();
217
218 /* Remove old registry elements */
219 rcu_gc_registry();
220
221 /*
222 * Wait for readers to observe original parity or be quiescent.
223 */
224 wait_for_readers();
225
226 /*
227 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
228 * model easier to understand. It does not have a big performance impact
229 * anyway, given this is the write-side.
230 */
231 cmm_smp_mb();
232
233 /* Switch parity: 0 -> 1, 1 -> 0 */
234 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
235
236 /*
237 * Must commit qparity update to memory before waiting for other parity
238 * quiescent state. Failure to do so could result in the writer waiting
239 * forever while new readers are always accessing data (no progress).
240 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
241 */
242
243 /*
244 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
245 * model easier to understand. It does not have a big performance impact
246 * anyway, given this is the write-side.
247 */
248 cmm_smp_mb();
249
250 /*
251 * Wait for readers to observe new parity or be quiescent.
252 */
253 wait_for_readers();
254
255 /*
256 * Finish waiting for reader threads before letting the old ptr being
257 * freed.
258 */
259 cmm_smp_mb();
260out:
261 mutex_unlock(&rcu_gp_lock);
262 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
263 assert(!ret);
264}
265
266/*
267 * library wrappers to be used by non-LGPL compatible source code.
268 */
269
270void rcu_read_lock(void)
271{
272 _rcu_read_lock();
273}
274
275void rcu_read_unlock(void)
276{
277 _rcu_read_unlock();
278}
279
280/*
281 * only grow for now.
282 */
283static void resize_arena(struct registry_arena *arena, size_t len)
284{
285 void *new_arena;
286
287 if (!arena->p)
288 new_arena = mmap(arena->p, len,
289 PROT_READ | PROT_WRITE,
290 MAP_ANONYMOUS | MAP_PRIVATE,
291 -1, 0);
292 else
293 new_arena = mremap_wrapper(arena->p, arena->len,
294 len, MREMAP_MAYMOVE);
295 assert(new_arena != MAP_FAILED);
296
297 /*
298 * re-used the same region ?
299 */
300 if (new_arena == arena->p)
301 return;
302
303 bzero(new_arena + arena->len, len - arena->len);
304 arena->p = new_arena;
305}
306
307/* Called with signals off and mutex locked */
308static void add_thread(void)
309{
310 struct rcu_reader *rcu_reader_reg;
311
312 if (registry_arena.len
313 < registry_arena.used + sizeof(struct rcu_reader))
314 resize_arena(&registry_arena,
315 caa_max(registry_arena.len << 1, ARENA_INIT_ALLOC));
316 /*
317 * Find a free spot.
318 */
319 for (rcu_reader_reg = registry_arena.p;
320 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
321 rcu_reader_reg++) {
322 if (!rcu_reader_reg->alloc)
323 break;
324 }
325 rcu_reader_reg->alloc = 1;
326 registry_arena.used += sizeof(struct rcu_reader);
327
328 /* Add to registry */
329 rcu_reader_reg->tid = pthread_self();
330 assert(rcu_reader_reg->ctr == 0);
331 cds_list_add(&rcu_reader_reg->node, &registry);
332 URCU_TLS(rcu_reader) = rcu_reader_reg;
333}
334
335/* Called with signals off and mutex locked */
336static void rcu_gc_registry(void)
337{
338 struct rcu_reader *rcu_reader_reg;
339 pthread_t tid;
340 int ret;
341
342 for (rcu_reader_reg = registry_arena.p;
343 (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
344 rcu_reader_reg++) {
345 if (!rcu_reader_reg->alloc)
346 continue;
347 tid = rcu_reader_reg->tid;
348 ret = pthread_kill(tid, 0);
349 assert(ret != EINVAL);
350 if (ret == ESRCH) {
351 cds_list_del(&rcu_reader_reg->node);
352 rcu_reader_reg->ctr = 0;
353 rcu_reader_reg->alloc = 0;
354 registry_arena.used -= sizeof(struct rcu_reader);
355 }
356 }
357}
358
359/* Disable signals, take mutex, add to registry */
360void rcu_bp_register(void)
361{
362 sigset_t newmask, oldmask;
363 int ret;
364
365 ret = sigemptyset(&newmask);
366 assert(!ret);
367 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
368 assert(!ret);
369
370 /*
371 * Check if a signal concurrently registered our thread since
372 * the check in rcu_read_lock(). */
373 if (URCU_TLS(rcu_reader))
374 goto end;
375
376 mutex_lock(&rcu_gp_lock);
377 add_thread();
378 mutex_unlock(&rcu_gp_lock);
379end:
380 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
381 assert(!ret);
382}
383
384void rcu_bp_exit(void)
385{
386 if (registry_arena.p)
387 munmap(registry_arena.p, registry_arena.len);
388}
389
390/*
391 * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
392 * a concurrent thread executing with this same lock held. This ensures that the
393 * registry is in a coherent state in the child.
394 */
395void rcu_bp_before_fork(void)
396{
397 sigset_t newmask, oldmask;
398 int ret;
399
400 ret = sigemptyset(&newmask);
401 assert(!ret);
402 ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
403 assert(!ret);
404 mutex_lock(&rcu_gp_lock);
405 saved_fork_signal_mask = oldmask;
406}
407
408void rcu_bp_after_fork_parent(void)
409{
410 sigset_t oldmask;
411 int ret;
412
413 oldmask = saved_fork_signal_mask;
414 mutex_unlock(&rcu_gp_lock);
415 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
416 assert(!ret);
417}
418
419void rcu_bp_after_fork_child(void)
420{
421 sigset_t oldmask;
422 int ret;
423
424 rcu_gc_registry();
425 oldmask = saved_fork_signal_mask;
426 mutex_unlock(&rcu_gp_lock);
427 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
428 assert(!ret);
429}
430
431void *rcu_dereference_sym_bp(void *p)
432{
433 return _rcu_dereference(p);
434}
435
436void *rcu_set_pointer_sym_bp(void **p, void *v)
437{
438 cmm_wmb();
439 uatomic_set(p, v);
440 return v;
441}
442
443void *rcu_xchg_pointer_sym_bp(void **p, void *v)
444{
445 cmm_wmb();
446 return uatomic_xchg(p, v);
447}
448
449void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
450{
451 cmm_wmb();
452 return uatomic_cmpxchg(p, old, _new);
453}
454
455DEFINE_RCU_FLAVOR(rcu_flavor);
456
457#include "urcu-call-rcu-impl.h"
458#include "urcu-defer-impl.h"
This page took 0.023926 seconds and 4 git commands to generate.