[urcu.git] / urcu-static.h

#ifndef _URCU_STATIC_H
#define _URCU_STATIC_H

/*
 * urcu-static.h
 *
 * Userspace RCU header, to be included only in LGPL-compatible code.
 *
 * Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
 *
 * Credits for Paul E. McKenney <paulmck@linux.vnet.ibm.com>
 * for inspiration coming from the Linux kernel RCU and rcu-preempt.
 *
 * Distributed under LGPLv2.1
 *
 * IBM's contributions to this file may be relicensed under LGPLv2 or later.
 */

#include <stdlib.h>
#include <pthread.h>

#include <compiler.h>
#include <arch.h>

/*
 * Identify a shared load. A smp_rmc() or smp_mc() should come before the load.
 */
#define _LOAD_SHARED(p)	       ACCESS_ONCE(p)

/*
 * Load a data from shared memory, doing a cache flush if required.
 */
#define LOAD_SHARED(p)			\
	({				\
		smp_rmc();		\
		_LOAD_SHARED(p);	\
	})

/*
 * Identify a shared store. A smp_wmc() or smp_mc() should follow the store.
 */
#define _STORE_SHARED(x, v)	({ ACCESS_ONCE(x) = (v); })

/*
 * Store v into x, where x is located in shared memory. Performs the required
 * cache flush after writing. Returns v.
 */
#define STORE_SHARED(x, v)		\
	({				\
		_STORE_SHARED(x, v);	\
		smp_wmc();		\
		(v);			\
	})

/**
 * _rcu_dereference - reads (copy) a RCU-protected pointer to a local variable
 * into a RCU read-side critical section. The pointer can later be safely
 * dereferenced within the critical section.
 *
 * This ensures that the pointer copy is invariant thorough the whole critical
 * section.
 *
 * Inserts memory barriers on architectures that require them (currently only
 * Alpha) and documents which pointers are protected by RCU.
 *
 * Should match rcu_assign_pointer() or rcu_xchg_pointer().
 */

#define _rcu_dereference(p)     ({					\
				typeof(p) _________p1 = LOAD_SHARED(p); \
				smp_read_barrier_depends();		\
				(_________p1);				\
				})

/*
 * This code section can only be included in LGPL 2.1 compatible source code.
 * See below for the function call wrappers which can be used in code meant to
 * be only linked with the Userspace RCU library. This comes with a small
 * performance degradation on the read-side due to the added function calls.
 * This is required to permit relinking with newer versions of the library.
 */

/*
 * The signal number used by the RCU library can be overridden with
 * -DSIGURCU= when compiling the library.
 */
#ifndef SIGURCU
#define SIGURCU SIGUSR1
#endif

/*
 * If a reader is really non-cooperative and refuses to commit its
 * urcu_active_readers count to memory (there is no barrier in the reader
 * per-se), kick it after a few loops waiting for it.
 */
#define KICK_READER_LOOPS 10000

#ifdef DEBUG_YIELD
#include <sched.h>
#include <time.h>
#include <pthread.h>
#include <unistd.h>

#define YIELD_READ 	(1 << 0)
#define YIELD_WRITE	(1 << 1)

/* Updates without DEBUG_FULL_MB are much slower. Account this in the delay */
#ifdef DEBUG_FULL_MB
/* maximum sleep delay, in us */
#define MAX_SLEEP 50
#else
#define MAX_SLEEP 30000
#endif

extern unsigned int yield_active;
extern unsigned int __thread rand_yield;

static inline void debug_yield_read(void)
{
	if (yield_active & YIELD_READ)
		if (rand_r(&rand_yield) & 0x1)
			usleep(rand_r(&rand_yield) % MAX_SLEEP);
}

static inline void debug_yield_write(void)
{
	if (yield_active & YIELD_WRITE)
		if (rand_r(&rand_yield) & 0x1)
			usleep(rand_r(&rand_yield) % MAX_SLEEP);
}

static inline void debug_yield_init(void)
{
	rand_yield = time(NULL) ^ pthread_self();
}
#else
static inline void debug_yield_read(void)
{
}

static inline void debug_yield_write(void)
{
}

static inline void debug_yield_init(void)
{

}
#endif

#ifdef DEBUG_FULL_MB
static inline void reader_barrier()
{
	smp_mb();
}
#else
static inline void reader_barrier()
{
	barrier();
}
#endif

/*
 * The trick here is that RCU_GP_CTR_BIT must be a multiple of 8 so we can use a
 * full 8-bits, 16-bits or 32-bits bitmask for the lower order bits.
 */
#define RCU_GP_COUNT		(1UL << 0)
/* Use the amount of bits equal to half of the architecture long size */
#define RCU_GP_CTR_BIT		(1UL << (sizeof(long) << 2))
#define RCU_GP_CTR_NEST_MASK	(RCU_GP_CTR_BIT - 1)

/*
 * Global quiescent period counter with low-order bits unused.
 * Using a int rather than a char to eliminate false register dependencies
 * causing stalls on some architectures.
 */
extern long urcu_gp_ctr;

extern long __thread urcu_active_readers;

static inline int rcu_old_gp_ongoing(long *value)
{
	long v;

	if (value == NULL)
		return 0;
	/*
	 * Make sure both tests below are done on the same version of *value
	 * to insure consistency.
	 */
	v = LOAD_SHARED(*value);
	return (v & RCU_GP_CTR_NEST_MASK) &&
		 ((v ^ urcu_gp_ctr) & RCU_GP_CTR_BIT);
}

static inline void _rcu_read_lock(void)
{
	long tmp;

	tmp = urcu_active_readers;
	/* urcu_gp_ctr = RCU_GP_COUNT | (~RCU_GP_CTR_BIT or RCU_GP_CTR_BIT) */
	/*
	 * The data dependency "read urcu_gp_ctr, write urcu_active_readers",
	 * serializes those two memory operations. The memory barrier in the
	 * signal handler ensures we receive the proper memory commit barriers
	 * required by _STORE_SHARED and _LOAD_SHARED whenever communication
	 * with the writer is needed.
	 */
	if (likely(!(tmp & RCU_GP_CTR_NEST_MASK)))
		_STORE_SHARED(urcu_active_readers, _LOAD_SHARED(urcu_gp_ctr));
	else
		_STORE_SHARED(urcu_active_readers, tmp + RCU_GP_COUNT);
	/*
	 * Increment active readers count before accessing the pointer.
	 * See force_mb_all_threads().
	 */
	reader_barrier();
}

static inline void _rcu_read_unlock(void)
{
	reader_barrier();
	/*
	 * Finish using rcu before decrementing the pointer.
	 * See force_mb_all_threads().
	 */
	_STORE_SHARED(urcu_active_readers, urcu_active_readers - RCU_GP_COUNT);
}

/**
 * _rcu_assign_pointer - assign (publicize) a pointer to a new data structure
 * meant to be read by RCU read-side critical sections. Returns the assigned
 * value.
 *
 * Documents which pointers will be dereferenced by RCU read-side critical
 * sections and adds the required memory barriers on architectures requiring
 * them. It also makes sure the compiler does not reorder code initializing the
 * data structure before its publication.
 *
 * Should match rcu_dereference_pointer().
 */

#define _rcu_assign_pointer(p, v)			\
	({						\
		if (!__builtin_constant_p(v) || 	\
		    ((v) != NULL))			\
			wmb();				\
		STORE_SHARED(p, v);			\
	})

/**
 * _rcu_xchg_pointer - same as rcu_assign_pointer, but returns the previous
 * pointer to the data structure, which can be safely freed after waitin for a
 * quiescent state using synchronize_rcu().
 */

#define _rcu_xchg_pointer(p, v)				\
	({						\
		if (!__builtin_constant_p(v) ||		\
		    ((v) != NULL))			\
			wmb();				\
		xchg(p, v);				\
	})

/*
 * Exchanges the pointer and waits for quiescent state.
 * The pointer returned can be freed.
 */
#define _rcu_publish_content(p, v)			\
	({						\
		void *oldptr;				\
		oldptr = _rcu_xchg_pointer(p, v);	\
		synchronize_rcu();			\
		oldptr;					\
	})

#endif /* _URCU_STATIC_H */
Commit	Line	Data
	1	#ifndef _URCU_STATIC_H
	2	#define _URCU_STATIC_H
	3
	4	/*
	5	* urcu-static.h
	6	*
	7	* Userspace RCU header, to be included only in LGPL-compatible code.
	8	*
	9	* Copyright February 2009 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
	10	*
	11	* Credits for Paul E. McKenney <paulmck@linux.vnet.ibm.com>
	12	* for inspiration coming from the Linux kernel RCU and rcu-preempt.
	13	*
	14	* Distributed under LGPLv2.1
	15	*
	16	* IBM's contributions to this file may be relicensed under LGPLv2 or later.
	17	*/
	18
	19	#include <stdlib.h>
	20	#include <pthread.h>
	21
	22	#include <compiler.h>
	23	#include <arch.h>
	24
	25	/*
	26	* Identify a shared load. A smp_rmc() or smp_mc() should come before the load.
	27	*/
	28	#define _LOAD_SHARED(p) ACCESS_ONCE(p)
	29
	30	/*
	31	* Load a data from shared memory, doing a cache flush if required.
	32	*/
	33	#define LOAD_SHARED(p) \
	34	({ \
	35	smp_rmc(); \
	36	_LOAD_SHARED(p); \
	37	})
	38
	39	/*
	40	* Identify a shared store. A smp_wmc() or smp_mc() should follow the store.
	41	*/
	42	#define _STORE_SHARED(x, v) ({ ACCESS_ONCE(x) = (v); })
	43
	44	/*
	45	* Store v into x, where x is located in shared memory. Performs the required
	46	* cache flush after writing. Returns v.
	47	*/
	48	#define STORE_SHARED(x, v) \
	49	({ \
	50	_STORE_SHARED(x, v); \
	51	smp_wmc(); \
	52	(v); \
	53	})
	54
	55	/**
	56	* _rcu_dereference - reads (copy) a RCU-protected pointer to a local variable
	57	* into a RCU read-side critical section. The pointer can later be safely
	58	* dereferenced within the critical section.
	59	*
	60	* This ensures that the pointer copy is invariant thorough the whole critical
	61	* section.
	62	*
	63	* Inserts memory barriers on architectures that require them (currently only
	64	* Alpha) and documents which pointers are protected by RCU.
	65	*
	66	* Should match rcu_assign_pointer() or rcu_xchg_pointer().
	67	*/
	68
	69	#define _rcu_dereference(p) ({ \
	70	typeof(p) _________p1 = LOAD_SHARED(p); \
	71	smp_read_barrier_depends(); \
	72	(_________p1); \
	73	})
	74
	75	/*
	76	* This code section can only be included in LGPL 2.1 compatible source code.
	77	* See below for the function call wrappers which can be used in code meant to
	78	* be only linked with the Userspace RCU library. This comes with a small
	79	* performance degradation on the read-side due to the added function calls.
	80	* This is required to permit relinking with newer versions of the library.
	81	*/
	82
	83	/*
	84	* The signal number used by the RCU library can be overridden with
	85	* -DSIGURCU= when compiling the library.
	86	*/
	87	#ifndef SIGURCU
	88	#define SIGURCU SIGUSR1
	89	#endif
	90
	91	/*
	92	* If a reader is really non-cooperative and refuses to commit its
	93	* urcu_active_readers count to memory (there is no barrier in the reader
	94	* per-se), kick it after a few loops waiting for it.
	95	*/
	96	#define KICK_READER_LOOPS 10000
	97
	98	#ifdef DEBUG_YIELD
	99	#include <sched.h>
	100	#include <time.h>
	101	#include <pthread.h>
	102	#include <unistd.h>
	103
	104	#define YIELD_READ (1 << 0)
	105	#define YIELD_WRITE (1 << 1)
	106
	107	/* Updates without DEBUG_FULL_MB are much slower. Account this in the delay */
	108	#ifdef DEBUG_FULL_MB
	109	/* maximum sleep delay, in us */
	110	#define MAX_SLEEP 50
	111	#else
	112	#define MAX_SLEEP 30000
	113	#endif
	114
	115	extern unsigned int yield_active;
	116	extern unsigned int __thread rand_yield;
	117
	118	static inline void debug_yield_read(void)
	119	{
	120	if (yield_active & YIELD_READ)
	121	if (rand_r(&rand_yield) & 0x1)
	122	usleep(rand_r(&rand_yield) % MAX_SLEEP);
	123	}
	124
	125	static inline void debug_yield_write(void)
	126	{
	127	if (yield_active & YIELD_WRITE)
	128	if (rand_r(&rand_yield) & 0x1)
	129	usleep(rand_r(&rand_yield) % MAX_SLEEP);
	130	}
	131
	132	static inline void debug_yield_init(void)
	133	{
	134	rand_yield = time(NULL) ^ pthread_self();
	135	}
	136	#else
	137	static inline void debug_yield_read(void)
	138	{
	139	}
	140
	141	static inline void debug_yield_write(void)
	142	{
	143	}
	144
	145	static inline void debug_yield_init(void)
	146	{
	147
	148	}
	149	#endif
	150
	151	#ifdef DEBUG_FULL_MB
	152	static inline void reader_barrier()
	153	{
	154	smp_mb();
	155	}
	156	#else
	157	static inline void reader_barrier()
	158	{
	159	barrier();
	160	}
	161	#endif
	162
	163	/*
	164	* The trick here is that RCU_GP_CTR_BIT must be a multiple of 8 so we can use a
	165	* full 8-bits, 16-bits or 32-bits bitmask for the lower order bits.
	166	*/
	167	#define RCU_GP_COUNT (1UL << 0)
	168	/* Use the amount of bits equal to half of the architecture long size */
	169	#define RCU_GP_CTR_BIT (1UL << (sizeof(long) << 2))
	170	#define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BIT - 1)
	171
	172	/*
	173	* Global quiescent period counter with low-order bits unused.
	174	* Using a int rather than a char to eliminate false register dependencies
	175	* causing stalls on some architectures.
	176	*/
	177	extern long urcu_gp_ctr;
	178
	179	extern long __thread urcu_active_readers;
	180
	181	static inline int rcu_old_gp_ongoing(long *value)
	182	{
	183	long v;
	184
	185	if (value == NULL)
	186	return 0;
	187	/*
	188	* Make sure both tests below are done on the same version of *value
	189	* to insure consistency.
	190	*/
	191	v = LOAD_SHARED(*value);
	192	return (v & RCU_GP_CTR_NEST_MASK) &&
	193	((v ^ urcu_gp_ctr) & RCU_GP_CTR_BIT);
	194	}
	195
	196	static inline void _rcu_read_lock(void)
	197	{
	198	long tmp;
	199
	200	tmp = urcu_active_readers;
	201	/* urcu_gp_ctr = RCU_GP_COUNT \| (~RCU_GP_CTR_BIT or RCU_GP_CTR_BIT) */
	202	/*
	203	* The data dependency "read urcu_gp_ctr, write urcu_active_readers",
	204	* serializes those two memory operations. The memory barrier in the
	205	* signal handler ensures we receive the proper memory commit barriers
	206	* required by _STORE_SHARED and _LOAD_SHARED whenever communication
	207	* with the writer is needed.
	208	*/
	209	if (likely(!(tmp & RCU_GP_CTR_NEST_MASK)))
	210	_STORE_SHARED(urcu_active_readers, _LOAD_SHARED(urcu_gp_ctr));
	211	else
	212	_STORE_SHARED(urcu_active_readers, tmp + RCU_GP_COUNT);
	213	/*
	214	* Increment active readers count before accessing the pointer.
	215	* See force_mb_all_threads().
	216	*/
	217	reader_barrier();
	218	}
	219
	220	static inline void _rcu_read_unlock(void)
	221	{
	222	reader_barrier();
	223	/*
	224	* Finish using rcu before decrementing the pointer.
	225	* See force_mb_all_threads().
	226	*/
	227	_STORE_SHARED(urcu_active_readers, urcu_active_readers - RCU_GP_COUNT);
	228	}
	229
	230	/**
	231	* _rcu_assign_pointer - assign (publicize) a pointer to a new data structure
	232	* meant to be read by RCU read-side critical sections. Returns the assigned
	233	* value.
	234	*
	235	* Documents which pointers will be dereferenced by RCU read-side critical
	236	* sections and adds the required memory barriers on architectures requiring
	237	* them. It also makes sure the compiler does not reorder code initializing the
	238	* data structure before its publication.
	239	*
	240	* Should match rcu_dereference_pointer().
	241	*/
	242
	243	#define _rcu_assign_pointer(p, v) \
	244	({ \
	245	if (!__builtin_constant_p(v) \|\| \
	246	((v) != NULL)) \
	247	wmb(); \
	248	STORE_SHARED(p, v); \
	249	})
	250
	251	/**
	252	* _rcu_xchg_pointer - same as rcu_assign_pointer, but returns the previous
	253	* pointer to the data structure, which can be safely freed after waitin for a
	254	* quiescent state using synchronize_rcu().
	255	*/
	256
	257	#define _rcu_xchg_pointer(p, v) \
	258	({ \
	259	if (!__builtin_constant_p(v) \|\| \
	260	((v) != NULL)) \
	261	wmb(); \
	262	xchg(p, v); \
	263	})
	264
	265	/*
	266	* Exchanges the pointer and waits for quiescent state.
	267	* The pointer returned can be freed.
	268	*/
	269	#define _rcu_publish_content(p, v) \
	270	({ \
	271	void *oldptr; \
	272	oldptr = _rcu_xchg_pointer(p, v); \
	273	synchronize_rcu(); \
	274	oldptr; \
	275	})
	276
	277	#endif /* _URCU_STATIC_H */