7c91e0a9ce8bb40b3ef688011cc0cc9cf933b536
[urcu.git] / urcu-bp.c
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__
55 static
56 void *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 */
70 static
71 void *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
101 void __attribute__((destructor)) rcu_bp_exit(void);
102
103 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
104
105 #ifdef DEBUG_YIELD
106 unsigned int yield_active;
107 DEFINE_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 */
116 long 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 */
122 DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
123
124 static CDS_LIST_HEAD(registry);
125
126 struct registry_arena {
127 void *p;
128 size_t len;
129 size_t used;
130 };
131
132 static struct registry_arena registry_arena;
133
134 /* Saved fork signal mask, protected by rcu_gp_lock */
135 static sigset_t saved_fork_signal_mask;
136
137 static void rcu_gc_registry(void);
138
139 static 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
161 static 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
172 void 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
218 void 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();
263 out:
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
273 void rcu_read_lock(void)
274 {
275 _rcu_read_lock();
276 }
277
278 void rcu_read_unlock(void)
279 {
280 _rcu_read_unlock();
281 }
282
283 /*
284 * only grow for now.
285 */
286 static 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 */
311 static 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 */
339 static 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 */
363 void 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);
382 end:
383 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
384 assert(!ret);
385 }
386
387 void 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 */
398 void 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
411 void 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
422 void 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
434 void *rcu_dereference_sym_bp(void *p)
435 {
436 return _rcu_dereference(p);
437 }
438
439 void *rcu_set_pointer_sym_bp(void **p, void *v)
440 {
441 cmm_wmb();
442 return uatomic_set(p, v);
443 }
444
445 void *rcu_xchg_pointer_sym_bp(void **p, void *v)
446 {
447 cmm_wmb();
448 return uatomic_xchg(p, v);
449 }
450
451 void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
452 {
453 cmm_wmb();
454 return uatomic_cmpxchg(p, old, _new);
455 }
456
457 DEFINE_RCU_FLAVOR(rcu_flavor);
458
459 #include "urcu-call-rcu-impl.h"
460 #include "urcu-defer-impl.h"
This page took 0.061786 seconds and 3 git commands to generate.