cds_lfht_replace: add checks for old/new node hash/value match
[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
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*/
62void *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
91void __attribute__((destructor)) rcu_bp_exit(void);
92
93static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
94
95#ifdef DEBUG_YIELD
96unsigned int yield_active;
97unsigned 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 */
106long 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 */
112struct rcu_reader __thread *rcu_reader;
113
114static CDS_LIST_HEAD(registry);
115
116struct registry_arena {
117 void *p;
118 size_t len;
119 size_t used;
120};
121
122static struct registry_arena registry_arena;
123
124/* Saved fork signal mask, protected by rcu_gp_lock */
125static sigset_t saved_fork_signal_mask;
126
127static void rcu_gc_registry(void);
128
129static 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
151static 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
162void 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
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
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();
253out:
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
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
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 */
301static 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 */
329static 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 */
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(). */
366 if (rcu_reader)
367 goto end;
368
369 mutex_lock(&rcu_gp_lock);
370 add_thread();
371 mutex_unlock(&rcu_gp_lock);
372end:
373 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
374 assert(!ret);
375}
376
377void 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 */
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}
423
424void *rcu_dereference_sym_bp(void *p)
425{
426 return _rcu_dereference(p);
427}
428
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
447DEFINE_RCU_FLAVOR(rcu_flavor);
448
449#include "urcu-call-rcu-impl.h"
450#include "urcu-defer-impl.h"
This page took 0.024954 seconds and 4 git commands to generate.