Tests fix: add missing Cygwin thread id
[urcu.git] / src / 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 _LGPL_SOURCE
27#include <stdio.h>
28#include <pthread.h>
29#include <signal.h>
30#include <assert.h>
31#include <stdlib.h>
32#include <string.h>
33#include <errno.h>
34#include <poll.h>
35#include <unistd.h>
36#include <sys/mman.h>
37
38#include "urcu/arch.h"
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 not allowing MAYMOVE.
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 assert(!(flags & MREMAP_MAYMOVE));
77
78 return MAP_FAILED;
79}
80#endif
81
82/* Sleep delay in ms */
83#define RCU_SLEEP_DELAY_MS 10
84#define INIT_NR_THREADS 8
85#define ARENA_INIT_ALLOC \
86 sizeof(struct registry_chunk) \
87 + INIT_NR_THREADS * sizeof(struct rcu_reader)
88
89/*
90 * Active attempts to check for reader Q.S. before calling sleep().
91 */
92#define RCU_QS_ACTIVE_ATTEMPTS 100
93
94static
95int rcu_bp_refcount;
96
97/* If the headers do not support membarrier system call, fall back smp_mb. */
98#ifdef __NR_membarrier
99# define membarrier(...) syscall(__NR_membarrier, __VA_ARGS__)
100#else
101# define membarrier(...) -ENOSYS
102#endif
103
104enum membarrier_cmd {
105 MEMBARRIER_CMD_QUERY = 0,
106 MEMBARRIER_CMD_SHARED = (1 << 0),
107};
108
109static
110void __attribute__((constructor)) rcu_bp_init(void);
111static
112void __attribute__((destructor)) rcu_bp_exit(void);
113
114#ifndef CONFIG_RCU_FORCE_SYS_MEMBARRIER
115int urcu_bp_has_sys_membarrier;
116#endif
117
118/*
119 * rcu_gp_lock ensures mutual exclusion between threads calling
120 * synchronize_rcu().
121 */
122static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;
123/*
124 * rcu_registry_lock ensures mutual exclusion between threads
125 * registering and unregistering themselves to/from the registry, and
126 * with threads reading that registry from synchronize_rcu(). However,
127 * this lock is not held all the way through the completion of awaiting
128 * for the grace period. It is sporadically released between iterations
129 * on the registry.
130 * rcu_registry_lock may nest inside rcu_gp_lock.
131 */
132static pthread_mutex_t rcu_registry_lock = PTHREAD_MUTEX_INITIALIZER;
133
134static pthread_mutex_t init_lock = PTHREAD_MUTEX_INITIALIZER;
135static int initialized;
136
137static pthread_key_t urcu_bp_key;
138
139struct rcu_gp rcu_gp = { .ctr = RCU_GP_COUNT };
140
141/*
142 * Pointer to registry elements. Written to only by each individual reader. Read
143 * by both the reader and the writers.
144 */
145DEFINE_URCU_TLS(struct rcu_reader *, rcu_reader);
146
147static CDS_LIST_HEAD(registry);
148
149struct registry_chunk {
150 size_t data_len; /* data length */
151 size_t used; /* amount of data used */
152 struct cds_list_head node; /* chunk_list node */
153 char data[];
154};
155
156struct registry_arena {
157 struct cds_list_head chunk_list;
158};
159
160static struct registry_arena registry_arena = {
161 .chunk_list = CDS_LIST_HEAD_INIT(registry_arena.chunk_list),
162};
163
164/* Saved fork signal mask, protected by rcu_gp_lock */
165static sigset_t saved_fork_signal_mask;
166
167static void mutex_lock(pthread_mutex_t *mutex)
168{
169 int ret;
170
171#ifndef DISTRUST_SIGNALS_EXTREME
172 ret = pthread_mutex_lock(mutex);
173 if (ret)
174 urcu_die(ret);
175#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
176 while ((ret = pthread_mutex_trylock(mutex)) != 0) {
177 if (ret != EBUSY && ret != EINTR)
178 urcu_die(ret);
179 poll(NULL,0,10);
180 }
181#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
182}
183
184static void mutex_unlock(pthread_mutex_t *mutex)
185{
186 int ret;
187
188 ret = pthread_mutex_unlock(mutex);
189 if (ret)
190 urcu_die(ret);
191}
192
193static void smp_mb_master(void)
194{
195 if (caa_likely(urcu_bp_has_sys_membarrier))
196 (void) membarrier(MEMBARRIER_CMD_SHARED, 0);
197 else
198 cmm_smp_mb();
199}
200
201/*
202 * Always called with rcu_registry lock held. Releases this lock between
203 * iterations and grabs it again. Holds the lock when it returns.
204 */
205static void wait_for_readers(struct cds_list_head *input_readers,
206 struct cds_list_head *cur_snap_readers,
207 struct cds_list_head *qsreaders)
208{
209 unsigned int wait_loops = 0;
210 struct rcu_reader *index, *tmp;
211
212 /*
213 * Wait for each thread URCU_TLS(rcu_reader).ctr to either
214 * indicate quiescence (not nested), or observe the current
215 * rcu_gp.ctr value.
216 */
217 for (;;) {
218 if (wait_loops < RCU_QS_ACTIVE_ATTEMPTS)
219 wait_loops++;
220
221 cds_list_for_each_entry_safe(index, tmp, input_readers, node) {
222 switch (rcu_reader_state(&index->ctr)) {
223 case RCU_READER_ACTIVE_CURRENT:
224 if (cur_snap_readers) {
225 cds_list_move(&index->node,
226 cur_snap_readers);
227 break;
228 }
229 /* Fall-through */
230 case RCU_READER_INACTIVE:
231 cds_list_move(&index->node, qsreaders);
232 break;
233 case RCU_READER_ACTIVE_OLD:
234 /*
235 * Old snapshot. Leaving node in
236 * input_readers will make us busy-loop
237 * until the snapshot becomes current or
238 * the reader becomes inactive.
239 */
240 break;
241 }
242 }
243
244 if (cds_list_empty(input_readers)) {
245 break;
246 } else {
247 /* Temporarily unlock the registry lock. */
248 mutex_unlock(&rcu_registry_lock);
249 if (wait_loops >= RCU_QS_ACTIVE_ATTEMPTS)
250 (void) poll(NULL, 0, RCU_SLEEP_DELAY_MS);
251 else
252 caa_cpu_relax();
253 /* Re-lock the registry lock before the next loop. */
254 mutex_lock(&rcu_registry_lock);
255 }
256 }
257}
258
259void synchronize_rcu(void)
260{
261 CDS_LIST_HEAD(cur_snap_readers);
262 CDS_LIST_HEAD(qsreaders);
263 sigset_t newmask, oldmask;
264 int ret;
265
266 ret = sigfillset(&newmask);
267 assert(!ret);
268 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
269 assert(!ret);
270
271 mutex_lock(&rcu_gp_lock);
272
273 mutex_lock(&rcu_registry_lock);
274
275 if (cds_list_empty(&registry))
276 goto out;
277
278 /* All threads should read qparity before accessing data structure
279 * where new ptr points to. */
280 /* Write new ptr before changing the qparity */
281 smp_mb_master();
282
283 /*
284 * Wait for readers to observe original parity or be quiescent.
285 * wait_for_readers() can release and grab again rcu_registry_lock
286 * interally.
287 */
288 wait_for_readers(&registry, &cur_snap_readers, &qsreaders);
289
290 /*
291 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
292 * model easier to understand. It does not have a big performance impact
293 * anyway, given this is the write-side.
294 */
295 cmm_smp_mb();
296
297 /* Switch parity: 0 -> 1, 1 -> 0 */
298 CMM_STORE_SHARED(rcu_gp.ctr, rcu_gp.ctr ^ RCU_GP_CTR_PHASE);
299
300 /*
301 * Must commit qparity update to memory before waiting for other parity
302 * quiescent state. Failure to do so could result in the writer waiting
303 * forever while new readers are always accessing data (no progress).
304 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
305 */
306
307 /*
308 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
309 * model easier to understand. It does not have a big performance impact
310 * anyway, given this is the write-side.
311 */
312 cmm_smp_mb();
313
314 /*
315 * Wait for readers to observe new parity or be quiescent.
316 * wait_for_readers() can release and grab again rcu_registry_lock
317 * interally.
318 */
319 wait_for_readers(&cur_snap_readers, NULL, &qsreaders);
320
321 /*
322 * Put quiescent reader list back into registry.
323 */
324 cds_list_splice(&qsreaders, &registry);
325
326 /*
327 * Finish waiting for reader threads before letting the old ptr being
328 * freed.
329 */
330 smp_mb_master();
331out:
332 mutex_unlock(&rcu_registry_lock);
333 mutex_unlock(&rcu_gp_lock);
334 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
335 assert(!ret);
336}
337
338/*
339 * library wrappers to be used by non-LGPL compatible source code.
340 */
341
342void rcu_read_lock(void)
343{
344 _rcu_read_lock();
345}
346
347void rcu_read_unlock(void)
348{
349 _rcu_read_unlock();
350}
351
352int rcu_read_ongoing(void)
353{
354 return _rcu_read_ongoing();
355}
356
357/*
358 * Only grow for now. If empty, allocate a ARENA_INIT_ALLOC sized chunk.
359 * Else, try expanding the last chunk. If this fails, allocate a new
360 * chunk twice as big as the last chunk.
361 * Memory used by chunks _never_ moves. A chunk could theoretically be
362 * freed when all "used" slots are released, but we don't do it at this
363 * point.
364 */
365static
366void expand_arena(struct registry_arena *arena)
367{
368 struct registry_chunk *new_chunk, *last_chunk;
369 size_t old_chunk_len, new_chunk_len;
370
371 /* No chunk. */
372 if (cds_list_empty(&arena->chunk_list)) {
373 assert(ARENA_INIT_ALLOC >=
374 sizeof(struct registry_chunk)
375 + sizeof(struct rcu_reader));
376 new_chunk_len = ARENA_INIT_ALLOC;
377 new_chunk = (struct registry_chunk *) mmap(NULL,
378 new_chunk_len,
379 PROT_READ | PROT_WRITE,
380 MAP_ANONYMOUS | MAP_PRIVATE,
381 -1, 0);
382 if (new_chunk == MAP_FAILED)
383 abort();
384 memset(new_chunk, 0, new_chunk_len);
385 new_chunk->data_len =
386 new_chunk_len - sizeof(struct registry_chunk);
387 cds_list_add_tail(&new_chunk->node, &arena->chunk_list);
388 return; /* We're done. */
389 }
390
391 /* Try expanding last chunk. */
392 last_chunk = cds_list_entry(arena->chunk_list.prev,
393 struct registry_chunk, node);
394 old_chunk_len =
395 last_chunk->data_len + sizeof(struct registry_chunk);
396 new_chunk_len = old_chunk_len << 1;
397
398 /* Don't allow memory mapping to move, just expand. */
399 new_chunk = mremap_wrapper(last_chunk, old_chunk_len,
400 new_chunk_len, 0);
401 if (new_chunk != MAP_FAILED) {
402 /* Should not have moved. */
403 assert(new_chunk == last_chunk);
404 memset((char *) last_chunk + old_chunk_len, 0,
405 new_chunk_len - old_chunk_len);
406 last_chunk->data_len =
407 new_chunk_len - sizeof(struct registry_chunk);
408 return; /* We're done. */
409 }
410
411 /* Remap did not succeed, we need to add a new chunk. */
412 new_chunk = (struct registry_chunk *) mmap(NULL,
413 new_chunk_len,
414 PROT_READ | PROT_WRITE,
415 MAP_ANONYMOUS | MAP_PRIVATE,
416 -1, 0);
417 if (new_chunk == MAP_FAILED)
418 abort();
419 memset(new_chunk, 0, new_chunk_len);
420 new_chunk->data_len =
421 new_chunk_len - sizeof(struct registry_chunk);
422 cds_list_add_tail(&new_chunk->node, &arena->chunk_list);
423}
424
425static
426struct rcu_reader *arena_alloc(struct registry_arena *arena)
427{
428 struct registry_chunk *chunk;
429 struct rcu_reader *rcu_reader_reg;
430 int expand_done = 0; /* Only allow to expand once per alloc */
431 size_t len = sizeof(struct rcu_reader);
432
433retry:
434 cds_list_for_each_entry(chunk, &arena->chunk_list, node) {
435 if (chunk->data_len - chunk->used < len)
436 continue;
437 /* Find spot */
438 for (rcu_reader_reg = (struct rcu_reader *) &chunk->data[0];
439 rcu_reader_reg < (struct rcu_reader *) &chunk->data[chunk->data_len];
440 rcu_reader_reg++) {
441 if (!rcu_reader_reg->alloc) {
442 rcu_reader_reg->alloc = 1;
443 chunk->used += len;
444 return rcu_reader_reg;
445 }
446 }
447 }
448
449 if (!expand_done) {
450 expand_arena(arena);
451 expand_done = 1;
452 goto retry;
453 }
454
455 return NULL;
456}
457
458/* Called with signals off and mutex locked */
459static
460void add_thread(void)
461{
462 struct rcu_reader *rcu_reader_reg;
463 int ret;
464
465 rcu_reader_reg = arena_alloc(&registry_arena);
466 if (!rcu_reader_reg)
467 abort();
468 ret = pthread_setspecific(urcu_bp_key, rcu_reader_reg);
469 if (ret)
470 abort();
471
472 /* Add to registry */
473 rcu_reader_reg->tid = pthread_self();
474 assert(rcu_reader_reg->ctr == 0);
475 cds_list_add(&rcu_reader_reg->node, &registry);
476 /*
477 * Reader threads are pointing to the reader registry. This is
478 * why its memory should never be relocated.
479 */
480 URCU_TLS(rcu_reader) = rcu_reader_reg;
481}
482
483/* Called with mutex locked */
484static
485void cleanup_thread(struct registry_chunk *chunk,
486 struct rcu_reader *rcu_reader_reg)
487{
488 rcu_reader_reg->ctr = 0;
489 cds_list_del(&rcu_reader_reg->node);
490 rcu_reader_reg->tid = 0;
491 rcu_reader_reg->alloc = 0;
492 chunk->used -= sizeof(struct rcu_reader);
493}
494
495static
496struct registry_chunk *find_chunk(struct rcu_reader *rcu_reader_reg)
497{
498 struct registry_chunk *chunk;
499
500 cds_list_for_each_entry(chunk, &registry_arena.chunk_list, node) {
501 if (rcu_reader_reg < (struct rcu_reader *) &chunk->data[0])
502 continue;
503 if (rcu_reader_reg >= (struct rcu_reader *) &chunk->data[chunk->data_len])
504 continue;
505 return chunk;
506 }
507 return NULL;
508}
509
510/* Called with signals off and mutex locked */
511static
512void remove_thread(struct rcu_reader *rcu_reader_reg)
513{
514 cleanup_thread(find_chunk(rcu_reader_reg), rcu_reader_reg);
515 URCU_TLS(rcu_reader) = NULL;
516}
517
518/* Disable signals, take mutex, add to registry */
519void rcu_bp_register(void)
520{
521 sigset_t newmask, oldmask;
522 int ret;
523
524 ret = sigfillset(&newmask);
525 if (ret)
526 abort();
527 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
528 if (ret)
529 abort();
530
531 /*
532 * Check if a signal concurrently registered our thread since
533 * the check in rcu_read_lock().
534 */
535 if (URCU_TLS(rcu_reader))
536 goto end;
537
538 /*
539 * Take care of early registration before urcu_bp constructor.
540 */
541 rcu_bp_init();
542
543 mutex_lock(&rcu_registry_lock);
544 add_thread();
545 mutex_unlock(&rcu_registry_lock);
546end:
547 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
548 if (ret)
549 abort();
550}
551
552/* Disable signals, take mutex, remove from registry */
553static
554void rcu_bp_unregister(struct rcu_reader *rcu_reader_reg)
555{
556 sigset_t newmask, oldmask;
557 int ret;
558
559 ret = sigfillset(&newmask);
560 if (ret)
561 abort();
562 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
563 if (ret)
564 abort();
565
566 mutex_lock(&rcu_registry_lock);
567 remove_thread(rcu_reader_reg);
568 mutex_unlock(&rcu_registry_lock);
569 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
570 if (ret)
571 abort();
572 rcu_bp_exit();
573}
574
575/*
576 * Remove thread from the registry when it exits, and flag it as
577 * destroyed so garbage collection can take care of it.
578 */
579static
580void urcu_bp_thread_exit_notifier(void *rcu_key)
581{
582 rcu_bp_unregister(rcu_key);
583}
584
585#ifdef CONFIG_RCU_FORCE_SYS_MEMBARRIER
586static
587void rcu_sys_membarrier_status(int available)
588{
589 if (!available)
590 abort();
591}
592#else
593static
594void rcu_sys_membarrier_status(int available)
595{
596 if (available)
597 urcu_bp_has_sys_membarrier = 1;
598}
599#endif
600
601static
602void rcu_bp_init(void)
603{
604 mutex_lock(&init_lock);
605 if (!rcu_bp_refcount++) {
606 int ret;
607
608 ret = pthread_key_create(&urcu_bp_key,
609 urcu_bp_thread_exit_notifier);
610 if (ret)
611 abort();
612 ret = membarrier(MEMBARRIER_CMD_QUERY, 0);
613 rcu_sys_membarrier_status(ret >= 0
614 && (ret & MEMBARRIER_CMD_SHARED));
615 initialized = 1;
616 }
617 mutex_unlock(&init_lock);
618}
619
620static
621void rcu_bp_exit(void)
622{
623 mutex_lock(&init_lock);
624 if (!--rcu_bp_refcount) {
625 struct registry_chunk *chunk, *tmp;
626 int ret;
627
628 cds_list_for_each_entry_safe(chunk, tmp,
629 &registry_arena.chunk_list, node) {
630 munmap((void *) chunk, chunk->data_len
631 + sizeof(struct registry_chunk));
632 }
633 CDS_INIT_LIST_HEAD(&registry_arena.chunk_list);
634 ret = pthread_key_delete(urcu_bp_key);
635 if (ret)
636 abort();
637 }
638 mutex_unlock(&init_lock);
639}
640
641/*
642 * Holding the rcu_gp_lock and rcu_registry_lock across fork will make
643 * sure we fork() don't race with a concurrent thread executing with
644 * any of those locks held. This ensures that the registry and data
645 * protected by rcu_gp_lock are in a coherent state in the child.
646 */
647void rcu_bp_before_fork(void)
648{
649 sigset_t newmask, oldmask;
650 int ret;
651
652 ret = sigfillset(&newmask);
653 assert(!ret);
654 ret = pthread_sigmask(SIG_BLOCK, &newmask, &oldmask);
655 assert(!ret);
656 mutex_lock(&rcu_gp_lock);
657 mutex_lock(&rcu_registry_lock);
658 saved_fork_signal_mask = oldmask;
659}
660
661void rcu_bp_after_fork_parent(void)
662{
663 sigset_t oldmask;
664 int ret;
665
666 oldmask = saved_fork_signal_mask;
667 mutex_unlock(&rcu_registry_lock);
668 mutex_unlock(&rcu_gp_lock);
669 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
670 assert(!ret);
671}
672
673/*
674 * Prune all entries from registry except our own thread. Fits the Linux
675 * fork behavior. Called with rcu_gp_lock and rcu_registry_lock held.
676 */
677static
678void urcu_bp_prune_registry(void)
679{
680 struct registry_chunk *chunk;
681 struct rcu_reader *rcu_reader_reg;
682
683 cds_list_for_each_entry(chunk, &registry_arena.chunk_list, node) {
684 for (rcu_reader_reg = (struct rcu_reader *) &chunk->data[0];
685 rcu_reader_reg < (struct rcu_reader *) &chunk->data[chunk->data_len];
686 rcu_reader_reg++) {
687 if (!rcu_reader_reg->alloc)
688 continue;
689 if (rcu_reader_reg->tid == pthread_self())
690 continue;
691 cleanup_thread(chunk, rcu_reader_reg);
692 }
693 }
694}
695
696void rcu_bp_after_fork_child(void)
697{
698 sigset_t oldmask;
699 int ret;
700
701 urcu_bp_prune_registry();
702 oldmask = saved_fork_signal_mask;
703 mutex_unlock(&rcu_registry_lock);
704 mutex_unlock(&rcu_gp_lock);
705 ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
706 assert(!ret);
707}
708
709void *rcu_dereference_sym_bp(void *p)
710{
711 return _rcu_dereference(p);
712}
713
714void *rcu_set_pointer_sym_bp(void **p, void *v)
715{
716 cmm_wmb();
717 uatomic_set(p, v);
718 return v;
719}
720
721void *rcu_xchg_pointer_sym_bp(void **p, void *v)
722{
723 cmm_wmb();
724 return uatomic_xchg(p, v);
725}
726
727void *rcu_cmpxchg_pointer_sym_bp(void **p, void *old, void *_new)
728{
729 cmm_wmb();
730 return uatomic_cmpxchg(p, old, _new);
731}
732
733DEFINE_RCU_FLAVOR(rcu_flavor);
734
735#include "urcu-call-rcu-impl.h"
736#include "urcu-defer-impl.h"
This page took 0.025709 seconds and 4 git commands to generate.