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