Add rcu_flavor
[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
44 /* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
45 #undef _LGPL_SOURCE
46 #include "urcu-bp.h"
47 #define _LGPL_SOURCE
48
49 #ifndef MAP_ANONYMOUS
50 #define MAP_ANONYMOUS MAP_ANON
51 #endif
52
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 */
62 void *mremap(void *old_address, size_t old_size, size_t new_size, int flags)
63 {
64 void *new_address;
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
82 /* Sleep delay in us */
83 #define RCU_SLEEP_DELAY 1000
84 #define ARENA_INIT_ALLOC 16
85
86 /*
87 * Active attempts to check for reader Q.S. before calling sleep().
88 */
89 #define RCU_QS_ACTIVE_ATTEMPTS 100
90
91 void __attribute__((destructor)) rcu_bp_exit(void);
92
93 static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
94
95 #ifdef DEBUG_YIELD
96 unsigned int yield_active;
97 unsigned int __thread rand_yield;
98 #endif
99
100 /*
101 * Global grace period counter.
102 * Contains the current RCU_GP_CTR_PHASE.
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 */
106 long rcu_gp_ctr = RCU_GP_COUNT;
107
108 /*
109 * Pointer to registry elements. Written to only by each individual reader. Read
110 * by both the reader and the writers.
111 */
112 struct rcu_reader __thread *rcu_reader;
113
114 static CDS_LIST_HEAD(registry);
115
116 struct registry_arena {
117 void *p;
118 size_t len;
119 size_t used;
120 };
121
122 static struct registry_arena registry_arena;
123
124 /* Saved fork signal mask, protected by rcu_gp_lock */
125 static sigset_t saved_fork_signal_mask;
126
127 static void rcu_gc_registry(void);
128
129 static void mutex_lock(pthread_mutex_t *mutex)
130 {
131 int ret;
132
133 #ifndef DISTRUST_SIGNALS_EXTREME
134 ret = pthread_mutex_lock(mutex);
135 if (ret) {
136 perror("Error in pthread mutex lock");
137 exit(-1);
138 }
139 #else /* #ifndef DISTRUST_SIGNALS_EXTREME */
140 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
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 }
146 poll(NULL,0,10);
147 }
148 #endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
149 }
150
151 static void mutex_unlock(pthread_mutex_t *mutex)
152 {
153 int ret;
154
155 ret = pthread_mutex_unlock(mutex);
156 if (ret) {
157 perror("Error in pthread mutex unlock");
158 exit(-1);
159 }
160 }
161
162 void update_counter_and_wait(void)
163 {
164 CDS_LIST_HEAD(qsreaders);
165 int wait_loops = 0;
166 struct rcu_reader *index, *tmp;
167
168 /* Switch parity: 0 -> 1, 1 -> 0 */
169 CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);
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).
175 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
176 */
177
178 /*
179 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
180 * model easier to understand. It does not have a big performance impact
181 * anyway, given this is the write-side.
182 */
183 cmm_smp_mb();
184
185 /*
186 * Wait for each thread rcu_reader.ctr count to become 0.
187 */
188 for (;;) {
189 wait_loops++;
190 cds_list_for_each_entry_safe(index, tmp, &registry, node) {
191 if (!rcu_old_gp_ongoing(&index->ctr))
192 cds_list_move(&index->node, &qsreaders);
193 }
194
195 if (cds_list_empty(&registry)) {
196 break;
197 } else {
198 if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
199 usleep(RCU_SLEEP_DELAY);
200 else
201 caa_cpu_relax();
202 }
203 }
204 /* put back the reader list in the registry */
205 cds_list_splice(&qsreaders, &registry);
206 }
207
208 void 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
218 mutex_lock(&rcu_gp_lock);
219
220 if (cds_list_empty(&registry))
221 goto out;
222
223 /* All threads should read qparity before accessing data structure
224 * where new ptr points to. */
225 /* Write new ptr before changing the qparity */
226 cmm_smp_mb();
227
228 /* Remove old registry elements */
229 rcu_gc_registry();
230
231 /*
232 * Wait for previous parity to be empty of readers.
233 */
234 update_counter_and_wait(); /* 0 -> 1, wait readers in parity 0 */
235
236 /*
237 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
238 * model easier to understand. It does not have a big performance impact
239 * anyway, given this is the write-side.
240 */
241 cmm_smp_mb();
242
243 /*
244 * Wait for previous parity to be empty of readers.
245 */
246 update_counter_and_wait(); /* 1 -> 0, wait readers in parity 1 */
247
248 /*
249 * Finish waiting for reader threads before letting the old ptr being
250 * freed.
251 */
252 cmm_smp_mb();
253 out:
254 mutex_unlock(&rcu_gp_lock);
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
263 void rcu_read_lock(void)
264 {
265 _rcu_read_lock();
266 }
267
268 void rcu_read_unlock(void)
269 {
270 _rcu_read_unlock();
271 }
272
273 /*
274 * only grow for now.
275 */
276 static void resize_arena(struct registry_arena *arena, size_t len)
277 {
278 void *new_arena;
279
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
290 /*
291 * re-used the same region ?
292 */
293 if (new_arena == arena->p)
294 return;
295
296 bzero(new_arena + arena->len, len - arena->len);
297 arena->p = new_arena;
298 }
299
300 /* Called with signals off and mutex locked */
301 static void add_thread(void)
302 {
303 struct rcu_reader *rcu_reader_reg;
304
305 if (registry_arena.len
306 < registry_arena.used + sizeof(struct rcu_reader))
307 resize_arena(&registry_arena,
308 caa_max(registry_arena.len << 1, ARENA_INIT_ALLOC));
309 /*
310 * Find a free spot.
311 */
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)
316 break;
317 }
318 rcu_reader_reg->alloc = 1;
319 registry_arena.used += sizeof(struct rcu_reader);
320
321 /* Add to registry */
322 rcu_reader_reg->tid = pthread_self();
323 assert(rcu_reader_reg->ctr == 0);
324 cds_list_add(&rcu_reader_reg->node, &registry);
325 rcu_reader = rcu_reader_reg;
326 }
327
328 /* Called with signals off and mutex locked */
329 static void rcu_gc_registry(void)
330 {
331 struct rcu_reader *rcu_reader_reg;
332 pthread_t tid;
333 int ret;
334
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)
339 continue;
340 tid = rcu_reader_reg->tid;
341 ret = pthread_kill(tid, 0);
342 assert(ret != EINVAL);
343 if (ret == ESRCH) {
344 cds_list_del(&rcu_reader_reg->node);
345 rcu_reader_reg->ctr = 0;
346 rcu_reader_reg->alloc = 0;
347 registry_arena.used -= sizeof(struct rcu_reader);
348 }
349 }
350 }
351
352 /* Disable signals, take mutex, add to registry */
353 void 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(). */
366 if (rcu_reader)
367 goto end;
368
369 mutex_lock(&rcu_gp_lock);
370 add_thread();
371 mutex_unlock(&rcu_gp_lock);
372 end:
373 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
374 assert(!ret);
375 }
376
377 void rcu_bp_exit(void)
378 {
379 if (registry_arena.p)
380 munmap(registry_arena.p, registry_arena.len);
381 }
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 */
388 void 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
401 void 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
412 void 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 }
423
424 DEFINE_RCU_FLAVOR()
425
426 #include "urcu-call-rcu-impl.h"
427 #include "urcu-defer-impl.h"
This page took 0.056863 seconds and 4 git commands to generate.