[urcu.git] / urcu-bp.c

/*
 * urcu-bp.c
 *
 * Userspace RCU library, "bulletproof" version.
 *
 * Copyright (c) 2009 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
 * 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-bp-static.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)) urcu_bp_exit(void);

static pthread_mutex_t urcu_mutex = 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_BIT.
 * 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 urcu_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 urcu_reader __thread *urcu_reader;

static LIST_HEAD(registry);

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

static struct registry_arena registry_arena;

static void rcu_gc_registry(void);

static void internal_urcu_lock(void)
{
	int ret;

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

static void internal_urcu_unlock(void)
{
	int ret;

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

/*
 * called with urcu_mutex held.
 */
static void switch_next_urcu_qparity(void)
{
	STORE_SHARED(urcu_gp_ctr, urcu_gp_ctr ^ RCU_GP_CTR_BIT);
}

void wait_for_quiescent_state(void)
{
	LIST_HEAD(qsreaders);
	int wait_loops = 0;
	struct urcu_reader *index, *tmp;

	if (list_empty(&registry))
		return;
	/*
	 * Wait for each thread urcu_reader.ctr count to become 0.
	 */
	for (;;) {
		wait_loops++;
		list_for_each_entry_safe(index, tmp, &registry, head) {
			if (!rcu_old_gp_ongoing(&index->ctr))
				list_move(&index->head, &qsreaders);
		}

		if (list_empty(&registry)) {
			break;
		} else {
			if (wait_loops == RCU_QS_ACTIVE_ATTEMPTS)
				usleep(RCU_SLEEP_DELAY);
			else
				cpu_relax();
		}
	}
	/* put back the reader list in the registry */
	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);

	internal_urcu_lock();

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

	/* All threads should read qparity before accessing data structure
	 * where new ptr points to. Must be done within internal_urcu_lock
	 * because it iterates on reader threads.*/
	/* Write new ptr before changing the qparity */
	smp_mb();

	switch_next_urcu_qparity();	/* 0 -> 1 */

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

	/*
	 * Adding a 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.
	 */
	smp_mb();

	/*
	 * Wait for previous parity to be empty of readers.
	 */
	wait_for_quiescent_state();	/* Wait readers in parity 0 */

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

	/*
	 * Adding a 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.
	 */
	smp_mb();

	switch_next_urcu_qparity();	/* 1 -> 0 */

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

	/*
	 * Adding a 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.
	 */
	smp_mb();

	/*
	 * Wait for previous parity to be empty of readers.
	 */
	wait_for_quiescent_state();	/* Wait readers in parity 1 */

	/* Finish waiting for reader threads before letting the old ptr being
	 * freed. Must be done within internal_urcu_lock because it iterates on
	 * reader threads. */
	smp_mb();

	internal_urcu_unlock();
	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 urcu_reader *urcu_reader_reg;

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

	/* Add to registry */
	urcu_reader_reg->tid = pthread_self();
	assert(urcu_reader_reg->ctr == 0);
	list_add(&urcu_reader_reg->head, &registry);
	urcu_reader = urcu_reader_reg;
}

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

	for (urcu_reader_reg = registry_arena.p;
	     (void *)urcu_reader_reg < registry_arena.p + registry_arena.len;
	     urcu_reader_reg++) {
		if (!urcu_reader_reg->alloc)
			continue;
		tid = urcu_reader_reg->tid;
		ret = pthread_kill(tid, 0);
		assert(ret != EINVAL);
		if (ret == ESRCH) {
			list_del(&urcu_reader_reg->head);
			urcu_reader_reg->alloc = 0;
			registry_arena.used -= sizeof(struct urcu_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 (urcu_reader)
		goto end;

	internal_urcu_lock();
	add_thread();
	internal_urcu_unlock();
end:
	ret = pthread_sigmask(SIG_SETMASK, &oldmask, NULL);
	assert(!ret);
}

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