[urcu.git] / urcu-bp.c

/*
 * urcu-bp.c
 *
 * Userspace RCU library, "bulletproof" version.
 *
 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
 */

#define _GNU_SOURCE
#include <stdio.h>
#include <pthread.h>
#include <signal.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <poll.h>
#include <unistd.h>
#include <sys/mman.h>

#include "urcu/map/urcu-bp.h"

#include "urcu/static/urcu-bp.h"
/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */
#include "urcu-bp.h"

/* Sleep delay in us */
#define RCU_SLEEP_DELAY		1000
#define ARENA_INIT_ALLOC	16

void __attribute__((destructor)) rcu_bp_exit(void);

static pthread_mutex_t rcu_gp_lock = PTHREAD_MUTEX_INITIALIZER;

#ifdef DEBUG_YIELD
unsigned int yield_active;
unsigned int __thread rand_yield;
#endif

/*
 * Global grace period counter.
 * Contains the current RCU_GP_CTR_PHASE.
 * Also has a RCU_GP_COUNT of 1, to accelerate the reader fast path.
 * Written to only by writer with mutex taken. Read by both writer and readers.
 */
long rcu_gp_ctr = RCU_GP_COUNT;

/*
 * Pointer to registry elements. Written to only by each individual reader. Read
 * by both the reader and the writers.
 */
struct rcu_reader __thread *rcu_reader;

static CDS_LIST_HEAD(registry);

struct registry_arena {
	void *p;
	size_t len;
	size_t used;
};

static struct registry_arena registry_arena;

/* Saved fork signal mask, protected by rcu_gp_lock */
static sigset_t saved_fork_signal_mask;

static void rcu_gc_registry(void);

static void mutex_lock(pthread_mutex_t *mutex)
{
	int ret;

#ifndef DISTRUST_SIGNALS_EXTREME
	ret = pthread_mutex_lock(mutex);
	if (ret) {
		perror("Error in pthread mutex lock");
		exit(-1);
	}
#else /* #ifndef DISTRUST_SIGNALS_EXTREME */
	while ((ret = pthread_mutex_trylock(mutex)) != 0) {
		if (ret != EBUSY && ret != EINTR) {
			printf("ret = %d, errno = %d\n", ret, errno);
			perror("Error in pthread mutex lock");
			exit(-1);
		}
		poll(NULL,0,10);
	}
#endif /* #else #ifndef DISTRUST_SIGNALS_EXTREME */
}

static void mutex_unlock(pthread_mutex_t *mutex)
{
	int ret;

	ret = pthread_mutex_unlock(mutex);
	if (ret) {
		perror("Error in pthread mutex unlock");
		exit(-1);
	}
}

void update_counter_and_wait(void)
{
	CDS_LIST_HEAD(qsreaders);
	int wait_loops = 0;
	struct rcu_reader *index, *tmp;

	/* Switch parity: 0 -> 1, 1 -> 0 */
	CMM_STORE_SHARED(rcu_gp_ctr, rcu_gp_ctr ^ RCU_GP_CTR_PHASE);

	/*
	 * Must commit qparity update to memory before waiting for other parity
	 * quiescent state. Failure to do so could result in the writer waiting
	 * forever while new readers are always accessing data (no progress).
	 * Ensured by CMM_STORE_SHARED and CMM_LOAD_SHARED.
	 */

	/*
	 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
	 * model easier to understand. It does not have a big performance impact
	 * anyway, given this is the write-side.
	 */
	cmm_smp_mb();

	/*
	 * Wait for each thread rcu_reader.ctr count to become 0.
	 */
	for (;;) {
		wait_loops++;
		cds_list_for_each_entry_safe(index, tmp, &registry, node) {
			if (!rcu_old_gp_ongoing(&index->ctr))
				cds_list_move(&index->node, &qsreaders);
		}

		if (cds_list_empty(&registry)) {
			break;
		} else {
			if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
				usleep(RCU_SLEEP_DELAY);
			else
				caa_cpu_relax();
		}
	}
	/* put back the reader list in the registry */
	cds_list_splice(&qsreaders, &registry);
}

void synchronize_rcu(void)
{
	sigset_t newmask, oldmask;
	int ret;

	ret = sigemptyset(&newmask);
	assert(!ret);
	ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
	assert(!ret);

	mutex_lock(&rcu_gp_lock);

	if (cds_list_empty(&registry))
		goto out;

	/* All threads should read qparity before accessing data structure
	 * where new ptr points to. */
	/* Write new ptr before changing the qparity */
	cmm_smp_mb();

	/* Remove old registry elements */
	rcu_gc_registry();

	/*
	 * Wait for previous parity to be empty of readers.
	 */
	update_counter_and_wait();	/* 0 -> 1, wait readers in parity 0 */

	/*
	 * Adding a cmm_smp_mb() which is _not_ formally required, but makes the
	 * model easier to understand. It does not have a big performance impact
	 * anyway, given this is the write-side.
	 */
	cmm_smp_mb();

	/*
	 * Wait for previous parity to be empty of readers.
	 */
	update_counter_and_wait();	/* 1 -> 0, wait readers in parity 1 */

	/*
	 * Finish waiting for reader threads before letting the old ptr being
	 * freed.
	 */
	cmm_smp_mb();
out:
	mutex_unlock(&rcu_gp_lock);
	ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
	assert(!ret);
}

/*
 * library wrappers to be used by non-LGPL compatible source code.
 */

void rcu_read_lock(void)
{
	_rcu_read_lock();
}

void rcu_read_unlock(void)
{
	_rcu_read_unlock();
}

/*
 * only grow for now.
 */
static void resize_arena(struct registry_arena *arena, size_t len)
{
	void *new_arena;

	if (!arena->p)
		new_arena = mmap(arena->p, len,
				 PROT_READ | PROT_WRITE,
				 MAP_ANONYMOUS | MAP_PRIVATE,
				 -1, 0);
	else
		new_arena = mremap(arena->p, arena->len,
				   len, MREMAP_MAYMOVE);
	assert(new_arena != MAP_FAILED);

	/*
	 * re-used the same region ?
	 */
	if (new_arena == arena->p)
		return;

	memcpy(new_arena, arena->p, arena->len);
	bzero(new_arena + arena->len, len - arena->len);
	arena->p = new_arena;
}

/* Called with signals off and mutex locked */
static void add_thread(void)
{
	struct rcu_reader *rcu_reader_reg;

	if (registry_arena.len
	    < registry_arena.used + sizeof(struct rcu_reader))
		resize_arena(&registry_arena,
		max(registry_arena.len << 1, ARENA_INIT_ALLOC));
	/*
	 * Find a free spot.
	 */
	for (rcu_reader_reg = registry_arena.p;
	     (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
	     rcu_reader_reg++) {
		if (!rcu_reader_reg->alloc)
			break;
	}
	rcu_reader_reg->alloc = 1;
	registry_arena.used += sizeof(struct rcu_reader);

	/* Add to registry */
	rcu_reader_reg->tid = pthread_self();
	assert(rcu_reader_reg->ctr == 0);
	cds_list_add(&rcu_reader_reg->node, &registry);
	rcu_reader = rcu_reader_reg;
}

/* Called with signals off and mutex locked */
static void rcu_gc_registry(void)
{
	struct rcu_reader *rcu_reader_reg;
	pthread_t tid;
	int ret;

	for (rcu_reader_reg = registry_arena.p;
	     (void *)rcu_reader_reg < registry_arena.p + registry_arena.len;
	     rcu_reader_reg++) {
		if (!rcu_reader_reg->alloc)
			continue;
		tid = rcu_reader_reg->tid;
		ret = pthread_kill(tid, 0);
		assert(ret != EINVAL);
		if (ret == ESRCH) {
			cds_list_del(&rcu_reader_reg->node);
			rcu_reader_reg->ctr = 0;
			rcu_reader_reg->alloc = 0;
			registry_arena.used -= sizeof(struct rcu_reader);
		}
	}
}

/* Disable signals, take mutex, add to registry */
void rcu_bp_register(void)
{
	sigset_t newmask, oldmask;
	int ret;

	ret = sigemptyset(&newmask);
	assert(!ret);
	ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
	assert(!ret);

	/*
	 * Check if a signal concurrently registered our thread since
	 * the check in rcu_read_lock(). */
	if (rcu_reader)
		goto end;

	mutex_lock(&rcu_gp_lock);
	add_thread();
	mutex_unlock(&rcu_gp_lock);
end:
	ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
	assert(!ret);
}

void rcu_bp_exit()
{
	munmap(registry_arena.p, registry_arena.len);
}

/*
 * Holding the rcu_gp_lock across fork will make sure we fork() don't race with
 * a concurrent thread executing with this same lock held. This ensures that the
 * registry is in a coherent state in the child.
 */
void rcu_bp_before_fork(void)
{
	sigset_t newmask, oldmask;
	int ret;

	ret = sigemptyset(&newmask);
	assert(!ret);
	ret = pthread_sigmask(SIG_SETMASK, &newmask, &oldmask);
	assert(!ret);
	mutex_lock(&rcu_gp_lock);
	saved_fork_signal_mask = oldmask;
}

void rcu_bp_after_fork_parent(void)
{
	sigset_t oldmask;
	int ret;

	oldmask = saved_fork_signal_mask;
	mutex_unlock(&rcu_gp_lock);
	ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
	assert(!ret);
}

void rcu_bp_after_fork_child(void)
{
	sigset_t oldmask;
	int ret;

	rcu_gc_registry();
	oldmask = saved_fork_signal_mask;
	mutex_unlock(&rcu_gp_lock);
	ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
	assert(!ret);
}

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